Back to the main page

CO 750-1 Packing and Covering, Spring 2017

Course syllabus
Course notes

Lecture notes

    Lecture 1 (May 2): Introduction, Menger's theorem, Dilworth's theorem

    Lecture 2 (May 4): Integral polyhedra, totally dual integral systems

    Lecture 3 (May 9): Balanced matrices, bicolorings and k-colorings

    Lecture 4 (May 11): Integral polyhedra and totally dual integral systems associated to balanced matrices

    Lecture 5 (May 16): Hall's theorem for balanced hypergraphs, graph parameters χ ≥ ω, examples where equality holds

    Lecture 6 (May 18): Perfect graphs, the max-max inequality, the weak perfect graph theorem

    Lecture 7 (May 25): Odd holes and odd antiholes, the star cutset lemma, substitutions, balanced skew partitions

    Lecture 8 (May 30): The antitwin lemma, homogeneous pairs, 2-joins, the strong perfect graph theorem

    Lecture 9 (June 1): Integral and totally dual integral set packing programs corresponding to perfect graphs, perfect matrices, perfection implies total dual integrality, antiblocking polytopes

    Lecture 10 (June 6): The pluperfect graph theorem, clutters, antiblocking clutters, perfect clutters, the integral set packing polytopes

    Lecture 11 (June 8): The set covering polyhedron, blocking clutters, clutter parameters τ ≥ ν, examples where equality holds, ideal and Mengerian clutters

    Lecture 12 (June 13): The width-length inequality, clutter minors, strongly connected digraphs, dicuts

    Lecture 13 (June 15): The dicut coloring lemma, dijoins, the Lucchesi-Younger theorem, applications

    Lecture 14 (June 20): Cycles, circuits, T-joins, minimum cardinality T-joins, T-cuts, blocking relation, graft minors

    Lecture 15 (June 22): Packing T-cuts in bipartite graphs, the Edmonds-Johnson theorem, packing T-joins and the four color theorem

    Lecture 16 (June 27): Testing idealness, minimally non-ideal clutters, deltas (degenerate projective planes), finding delta minors

    Lecture 17 (June 29): Exclusive elements, tractability of deltas, intractability of odd holes, the set covering polytope, cross regular matrices

    Lecture 18 (July 4): Lehman's geometric characterization of minimally non-ideal clutters

    Lecture 19 (July 6): Lehman's combinatorial characterization of minimally non-ideal clutters, immediate applications to ideal clutters, the packing property

    Lecture 20 (July 11): Weakly bipartite graphs, planar graphs are weakly bipartite, signed graphs, odd circuits and signatures, signed graph minors, weakly bipartite signed graphs

    Lecture 21 (July 13): The whirlpool lemma, pseudo-odd-K5's, signed graphs without an odd-K5 minor are weakly bipartite

    Lecture 22 (July 18): Signed graphs without an odd-K5 minor are weakly bipartite, cube-ideal sets, twists, cuboids

    Lecture 23 (July 20): Coexclusive elements, ideal cuboids, binary spaces

    Lecture 24 (July 25): Cube-ideal binary spaces, the sums of circuits property, the cycle double cover conjecture