Part I: Connectivity, Matching, Flows, and Matroid theory

• 1/18: Introduction to k-connectivity, Mader's 1972 theorem connecting vertex degree and connectivity (pages 11-12), biconnectivity, block-cut point trees.

• 1/20: Menger's theorems, proof from first principles by Bohme, Goring, and Harant (1999) (pages 50-51).

• 1/25: No class.

• 1/27: Finished up proofs of Menger's theorems. Introduction to flow networks and flows, the max-flow problem.

• 2/1: The Ford-Fulkerson proof (1956) of the max-flow min-cut theorem (pages 125-128), a second proof of Menger's theorems using the max-flow min-cut thorem.

• 2/3: Matching in bipartite graphs, Konig-Egervary theorem (1931) and its proof from Menger's theorem, Hall's marriage theorem (1935) and its proof from Konig-Egervary theorem.

• 2/8: Tutte's 1-factor theorem (1947) and proof (page 35). statement and motivation of of Mader's H-path theorem (1978).
  Homework 1 assigned. Due 3/1.

• 2/10: Statement and motivation of of Mader's H-path theorem (1978). Implications of Mader's theorem.

• 2/15: Proof of Tutte's 1-factor theorem from Mader's theorem. Other implications of Mader's theorem. Introduction to the theorem of Tutte and Nash-Williams (1961) showing necessary and sufficient conditions on the existence of edge-disjoint spanning trees (pages 58-61).

• 2/17: Completion of the proof of the Tutte/Nash-Williams on edge-disjoint spanning trees.

• 2/22: Minimum cost k-connected spanning subgraph problem. Approximation algorithms. Introduction to Matroid theory.

• 2/24: Examples of matroids. Greedy algorithm for finding a maximum weight independent set in a matroid.

• 3/3: Transversal matroids, graphic matroids, cographic matroids. Motivation for Edmond's matroid intersection algorithm and matroid intersection theorem.

• 3/8: Proof of correctness of Edmond's poly-time algorithm for matroid intersection. Edmond's matroid intersection theorem.

• 3/10: Completed the proof of correctness of Edmond's matroid intersection theorem. Showed that Konig's matching theorem follows immediately from Edmond's matroid intersection theorem. Also showed how the Hamiltonian path problem in directed graphs reduces to the problem of finding the largest common independent set in three matroids.

Part II: Graph Coloring

• 3/22: Graph coloring. Brook's theorem, Konig's Theorem, and Vizing's theorem. Proof of Brook's theorem.
  Midterm handed out.

• 3/24: Proofs of Konig's Theorem and Vizing's theorem.
  Midterm due.

• 3/29: 5-colorability of planar graphs. A brief history of the 4-color theorem.

• 3/31 Introduction to list coloring. Thomassen's theorem on the 5-choosability of planar graphs.

• 4/5 Galvin's theorem that proves the list coloring conjecture for bipartite graphs.

• 4/8 Triangle-free graphs with large chromatic number (Mycielski's construction). Erdos' 1959 probabilistic construction of graphs with large girth and large chromatic number.

• 4/12 Erdos' construction of graphs with large girth and large chromatic number. Introduction to perfect graphs.

• 4/14 Examples of perfect graphs: interval graphs and chordal graphs.

• 4/19 A proof by Lovasz of the perfect graph theorem. Polyhedral results on perfect graphs.

• 4/21 Plan: Ellipsoid algorithm for optimally coloring perfect graphs in polynomial time.

Part III: Random Graphs and the Probabilistic Method