# MA252 Schedule

All references below are to sections of *A Course in Combinatorial Optimization* by A. Schrijver, unless otherwise stated.

**Week 1 (Jan 7-11): Introduction, Paths and Trees**

- Lecture 1: Introduction to combinatorial optimisation, graphs, directed graphs and linear programs. Lecture Notes

- Lecture 2: Shortest paths, Dijkstra's algorithm. Sections: 1.1, 1.2. See also Section 1.8 of Bondy and Murty.
- Lecture 3: Minimum spanning trees, Dijkstra-Prim Algorithm, Kruskal's Algorithm. Section: 1.4. See also Section 2.5 in Bondy and Murty.

**Week 2 (Jan 14-18): Linear Programming**

- Lecture 1: Basics of linear programs, setting up linear programs, polyhedra and polytopes. Sections 2.1, 2.2, 2.4. See also Goemans's notes here and here.
- Lecture 2: Farkas' Lemma, separating hyperplane theorem. Sections 2.1-2.3. See also Williamsons's notes here and here and Goemans's notes here.

- Lecture 3: Farkas' Lemma continued, linear programming duality. Section: 2.4. See also Goemans's notes here.

**Week 3 (Jan 21-25): Matchings in Bipartite Graphs**

- Lecture 1: Bipartite graphs, matchings, covers, Gallai's Theorem, Sections: 3.1, 3.2. See also Sections 5.1 of Bondy and Murty.
- Lecture 2: KÅ‘nig's Theorem, Hall's Marriage Theorem, bipartite matching algorithms. Sections: 3.3, 3.4. See also Sections 5.2, 5.4 and 5.5 of Bondy and Murty.
- Lecture 3: The matching polytope. Section: 3.5.

**Week 4 (Jan 28-Feb 1): Flow Problems**

- Lecture 1: Menger's Theorem. Section: 4.1. See also Section 11.4 of Bondy and Murty.
- Lecture 2: Max-Flow Min-Cut. Section: 4.2. See also Sections 11.1, 11.2 and 11.3 of Bondy and Murty.
- Lecture 3: Ford-Fulkerson Algorithm. Section: 4.3.

**Week 5 (Feb 4-8): Non-Bipartite Matching**

- Lecture 1: Tutte's Theorem, Tutte-Berge Formula. Section: 5.1. See also Section 5.3 of Bondy and Murty.
- Lecture 2: Matching algorithms. Sections: 5.2, 5.3.
- Lecture 3: Return of the matching polytope. Section: 5.4.

**Week 6 (Feb 11-15): Complexity Theory**

- Lecture 1: Algorithms, problems, running time. Sections: 6.1, 6.2, 6.3, 6.4.
- Lecture 2: NP, co-NP and completeness. Sections: 6.5, 6.6, 6.7
- Lecture 3: Proving NP-completeness. Sections: 6.8, 6.9.

**Week 7 (Feb 18-22): Cliques, stable sets and colourings**

- Lecture 1: Cliques and vertex colourings. Section: 7.1.
- Lecture 2: Edge colourings. Section: 7.2.
- Lecture 3: Perfect and chordal graphs. Sections: 7.4, 7.5.

**Week 8 (Feb 25-March 1): Treewidth and Dynamic Programming**

- Lecture 1: Tree decompositions, brambles and separators. Notes
^{1}Survey Paper

- Lecture 2: Tree decompositions, brambles and separators (continued).

- Lecture 3: Dynamic programming on graphs of bounded tree-width.

**Week 9 (March 4-8): Multicommodity Flows**

- Lecture 1: Introduction, two-commodity case. Sections: 9.1, 9.2.
- Lecture 2: Acyclic directed graphs. Section: 9.3.
- Lecture 3: On planar graphs. Section: 9.4.

**Week 10 (March 11-15): Matroids**

- Lecture 1: Introduction, greedy algorithms, equivalent axioms. Sections: 10.1, 10.2.
- Lecture 2: Examples of matroids, technical lemmas. Sections: 10.3, 10.4.
- Lecture 3: Edmonds' Matroid Intersection Theorem. Section: 10.5.

^{1}Permission to use these notes was generously given by the author, J. Erickson.