| Aug 23, 25, 30, Sep 1 | Notes 1-4 | Elementary properties of 2-edge-connected undirected graphs and strongly connected directed graphs. Degree constrained orientations. Minimum cut in undirected graphs. |
| Sep 6, 8, 13 | Notes 5-7 | Representation of minimum cuts. Gomory-Hu trees. Sparse certificates for edge- and node-connectivity. SFS trees. Chordal graphs. |
| Sep 13, 15, 20 | Notes 7-9 | Lucchesi-Younger theorem with algorithmic proof. Conservative costs. |
| Sep 20, 22 | Lectures 9-10 | Matroid theory basics: independence, cycle & rank axioms. Examples. Connected matroids. Operations: deletion, contraction, direct sum, truncation. Dual matroids. |
| Sep 27, 29 | No class. | |
| Homework set | Homework 1 | |
| Oct 4 | Lecture 11 | Greedy algorithm for matroids and polymatroids. Matroid and submodular polyhedra, matroids from polymatroids. Rado's theorem. Homomorphic image of matroids. Matroid partition theorem. |
| Oct 6 | Lecture 12 | Applications for matroid partition: packing and covering by trees. Matroid intersection, equivalence to matroid partition. Edmonds' algorithm for matroid intersection. Min-max formula for maximum weight common bases. |
| Oct 13 | Lecture 13 | Rooted k-edge connected subgraphs. Matroids from non-monotone submodular functions and from intersecting submodular functions. Truncation of intersecting submodular functions. Applications: source location, count matroids, rigidity matroid, Lovasz-Yemini theorem. |
| Oct 18 | Lecture 14 | Basics on integer polyhedra. TU-matrices: bipartite and directed graphs, network matrices and applications. TDI systems. |
| Oct 20 | Lecture 15 | TDI systems continued. Submodular flows. Edmonds-Giles theorem. Applications: flows, matroid intersection, Lucchesi-Younger, Nash-Williams's weak orientation theorem. See also lecture notes on Chandra Chekuri's website. |
| Oct 25 | Lecture 16 | Undirected splitting off: Lovász's theorem. Applications: constructive characterization of 2k-edge-connected graphs, Nash-Williams's weak orientation theorem. Mader's theorem on minimal k-edge-connected graphs. |
| Oct 27 | Lecture 17 | Undirected edge-connectivity augmentation. Degree-constrained version. Watanabe-Nakamura theorem. Matroidal structures. Minimum cost version for node-induced costs. Optimal augmentations with upper and lower bounds. Mader's undirected splitting off theorem (formulated). |
| Nov 1 | no lecture | Ravi Kannan's talk. |
| Nov 3 | Lecture 18 | Proof of Mader's undirected splitting off theorem. |
| Nov 8 | Lecture 19 | Undirected local edge-connectivity augmentation. Frank's theorem. Applications of splitting off: edge-disjoint Steiner-trees. Lovasz-Cherkassky theorem on T-paths. |
| Nov 10 | no lecture | Avi Wigderson's talk |
| Homework set | Homework 2 | |
| Nov 15,17 | no lecture | |
| Nov 22,29 | Lectures 20-21 | Mader's directed splitting off theorem. Directed edge-connectivity augmentation. Coverings of positively crossing supermodular set functions: degree prescribed version (Thm. 17.2.1) and minimum cardinality version (Thm. 17.2.8). Applications: subset connectivity, (k,l)-edge-connectivity. |
| Nov 24 | Thanksgiving | |
| Nov 29, 30 | Lectures 21-22 | Directed node-connectivity augmentation. Notion of set pairs: uncrossing, independence. Bisub/supermodular functions. Frank-Jordan theorem on covering positively crossing supermodular functions on set pairs. Applications: directed node-connectivity, ST-edge-connectivity augmentation, covering set pair functions. |
| Dec 1 | no lecture | Ruta Mehta's talk |
| Dec 5 | Lecture 23 | Gyori's theorems on generating path systems and on covering vertically convex rectilinear polygons. Frank's algorithm for finding an optimal solution. |
László Végh