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*