Back to my page

47853-A3 Special Topics in Combinatorial Optimization: Packing and Covering, Winter 2019

Course syllabus
Course notes (without citations)

I have summarized some of the open questions and conjectures in the field here.

Lecture notes

    Lecture 1 (Jan 15): Menger's theorem, Dilworth's theorem

    Lecture 2 (Jan 17): integral polyhedra, TDI linear systems, packing and covering models, balanced matrices

    Lecture 3 (Jan 22): characterization of balanced matrices, coloring balanced matrices and hypergraphs, integral polyhedra associated with balanced matrices

    Lecture 4 (Jan 24): Hall's theorem for balanced hypergrpahs, perfect graphs

    Lecture 5 (Jan 29): the max-max inequality, the weak perfect graph theorem, the star cutset lemma, substitution and duplication

    Lecture 6 (Feb 5): the antitwin lemma, the strong perfect graph theorem, TDI systems associated with perfect graphs

    Lecture 7 (Feb 7): perfect matrices, the pluperfect graph theorem, antiblocking theory, clutters

    Lecture 8 (Feb 12): blockers, ideal and Mengerian clutters, the width-length inequality, minor operations

    Lecture 9 (Feb 14): the Lucchesi-Younger theorem, Woodall's conjecture

    Lecture 10 (Feb 19): T-joins and T-cuts, packing T-cuts in bipartite graphs

    Lecture 11 (Feb 21): the Edmonds-Johnson theorem, the four color theorem, minimally nonideal clutters, the deltas

    Lecture 12 (Feb 26): finding delta minors, finding odd hole minors, cross regular matrices

    Lecture 13 (Feb 28): Lehman's characterizations of minimally nonideal clutters, consequences