MA252: Spring Term 2019 (Term 2)

Videos from the lectures are available on YouTube.

For each topic, the "main" source that I followed in the lecture is written in bold. Other sources are also included to provide students with other points of view.


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

• Lecture 1: Introduction to combinatorial optimisation, graphs, directed graphs and linear programs. Lecture notes written by me.
• Lecture 2: Shortest paths, Dijkstra's algorithm. Section 1.1 of Schrijver from below the proof of Theorem 1.2 until the end of Theorem 1.4. Section 1.8 of Bondy and Murty.
• Lecture 3: Minimum spanning trees, Dijkstra-Prim Algorithm, Kruskal's Algorithm. Section: 1.4 of Schrijver, except for Theorem 1.12. Section 2.5 in Bondy and Murty.

Week 1 Exercises
Some additional exercises (not all are relevant)
... and some more (not all are relevant)

Week 2 (Jan 14-18): Linear Programming

• Lecture 1: Basics of linear programs, setting up linear programs, polyhedra and polytopes. First section of Goemans's notes here and first two pages here. Bits of Sections 2.1-2.4 from Schrijver.
• Lecture 2: Farkas' Lemma, separating hyperplane theorem. Lecture notes written by me. Sections 2.1-2.3 of Schrijver, Williamsons's notes, his other notes and Goemans's notes.
• Lecture 3: Weak and strong duality for linear programs. Lecture notes written by me. Section 2.4 of Schrijver and Goemans's notes.

Week 2 Exercises
Some additional exercises (not all are relevant)
... and some more (not all are relevant)

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

• Lecture 1: Matchings, vertex covers, alternating/augmenting paths. Section 5.1 of Bondy and Murty. Section 3.1 of Schrijver except Gallai's Theorem, Section 3.2.
• Lecture 2: Bipartite graphs, Kőnig's Theorem, bipartite maximum matching algorithm. Kőnig's Theorem proof from lecture. Section 3.4 of Schrijver and Sections 5.2 and 5.4 of Bondy and Murty.
• Lecture 3: Bipartite maximum weight matching algorithm. The algorithm presented in the lecture can be found here and in Section 5.5 of Bondy and Murty.

Week 3 Exercises

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

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

Week 4 Exercises
Some additional exercises (not all are relevant)

Week 5 (Feb 4-8): Complexity Theory

• Lecture 1: Complexity classes, hardness. Lecture notes and video (from MIT)¹
• Lecture 2: Reductions, proving NP-hardness. SAT, k-SAT. Lecture notes from 2016 MA252 module.
• Lecture 3: More NP-hardness reductions. Cliques, stable sets, vertex covers. Proof that CLIQUE is NP-complete. Also, see Theorem 7.1 in Schrijver. Also, see Theorem 3.1 in Schrijver for a proof that the complement of an independent set is a vertex cover. Definition of the Clique problem can be found here.

Week 5 Exercises

Week 6 (Feb 11-15): Vertex Colouring

• Lecture 1: Vertex colouring, applications, bipartite graphs, a few great theorems (which we won't prove). Lecture notes written by me.
• Lecture 2: Hardness of vertex colouring, greedy algorithm, Brooks' Theorem (which we won't prove). Lecture notes written by me. See also Theorem 7.2 of Schrijver
• Lecture 3: Easy lower bounds on the chromatic number, perfect graphs, applications, examples. Lecture notes written by me. See also section 7.4 of Schrijver.

Week 6 Exercises

Week 7 (Feb 18-22): Perfect Graphs, Edge Colouring and Non-Bipartite Matching

• Lecture 1: Proof of The Weak Perfect Graph Theorem. Lecture notes written by me. See also Theorem 7.7 and Corollary 7.7a in Section 7.4 of Schrijver.
• Lecture 2: Edge colourings, edge colourings of bipartite graphs, Vizing's Theorem. Lecture notes written by me and Section 7.2 of Schrijver
• Lecture 3: Tutte's 1-Factor Theorem, Tutte-Berge Formula. Section: 5.1 of Schrijver. Section 5.3 of Bondy and Murty.

Week 7 Exercises

Week 8 (Feb 25-March 1): Integer Linear Programming

• Lecture 1: Integer linear programming, examples, writing problems as IPs, knapsack. Lecture notes written by me. Section 8.1 of Schrijver. Definition of the Knapsack Problem can be found here.
• Lecture 2: Totally unimodular matrices and polytopes. Lecture notes written by me. The start of Section 8.2 and Theorem 2.2 of Schrijver.
• Lecture 3: Totally unimodular matrices (continued) and TUMs from bipartite graphs. Lecture notes written by me. Theorems 8.2 and 8.3 of Schrijver.

Week 8 Exercises

Week 9 (March 4-8): Matching Polytope and Matroids

• Lecture 1: The matching polytope. Lecture notes written by me. Sections 8.3 and 5.4 of Schrijver.
• Lecture 2: Introduction to matroids, axioms, examples. Section 10.1, 10.3 of Schrijver. A very nice introduction to matroids can also be found in this article of Neel and Neudauer.
• Lecture 3: Greedy algorithms. Section 10.1 of Schrijver.

Week 10 (March 11-15): Matroids (cont'd)

• Lecture 1: Equivalent axioms, basis exchange, circuits. Sections 10.2 of Schrijver.
• Lecture 2: Preparation for Edmonds' Matroid Intersection Theorem (technical lemma). Lemma 10.2 in Schrijver.
• Lecture 3: Matroid intersection algorithm and Edmonds' Matroid Intersection Theorem. Section 10.5 of Schrijver.

Week 9/10 Exercises

¹This content is provided under a Creative Commons Licence.