Math 137a: Graph and Network Theory
Course Information:
- Professor: Padraic Bartlett.
- Class Time/Location: TTh 11-12:15am, Girvetz 1115.
- Office Hours: Tuesdays 1-2pm, South Hall 6516.
- Email: padraic at math dot ucsb dot edu.
- Syllabus: linked here.
Readings:
- Week 1: 1.1-1.5 of Diestel's Graph Theory; also, these notes on Prüfer sequences.
- Week 2: These notes on the Art Gallery Theorem.
- Week 2: I was traveling this week. Therefore, lectures were recorded and placed on YouTube! They're kind of awkward, because lecturing without an audience is odd, but you can watch them here: part 1/3, part 2/3,part 3/3.
- Week 3: Colorings, Euler Characteristic, and a (false) proof of the Four-Color Theorem. This corresponds loosely to sections 5.2, 5.1, and 4.2 of your text, though we have done only tiny bits of each section. Relevant notes that I wrote up: Mycielski graphs. Also, Thursday's talk on the Four-Color Theorem was based on Kempe's original proof; you can find corresponding notes on the course's Gauchospace (notes not linked here for copyright reasons.)
- Week 4: Perfect graphs. This all comes from section 5.5 of your textbook; we presented an alternate proof that all perfect graphs are chordal, and (on Thursday) proved that the complement of a perfect graph is perfect.
- Week 5: Spectral graph theory. Specifically, we finished proving that any graph is perfect iff its complement is perfect via the clever use of matrices, and on Thursday started studying other applications of matrices. Because our textbook does not talk about spectral methods much, I've posted an excerpt from Bollobas's text on spectral methods on Gauchospace.
- Week 6: Strongly regular graphs. This corresponds to some of the later stuff in Bollbas's text, and also some bits gleaned from this monograph on spectral graph theory.
- Week 7: Finishing our work on strongly regular graphs, and turning to Ramsey theory (which is chapter 9 of Diestel's text.)
- Week 8: The probabilistic method in graph theory, and random graphs (chapter 11 in Diestel, mostly.)
- Week 9/10: The Max-Flow/Min-Cut theorem and its applications; algebraic flows (chapter 6 in Diestel's text.)
Homework:
- Set 1: Basic graph theory. Due Tuesday, January 21.
- Set 2: Colorings of graphs. Due Tuesday, February 4.
- Set 3: Spectral graph theory. Due Thursday, February 20.
- Set 4: Strongly regular graphs, probabilistic methods, random graphs, Max-Flow/Min-Cut, and algebraic flows. Due Tuesday, March 11.
- Final: Everything. Due Friday, March 21, by 1pm.