Ahmad Abdi's webpage

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, q-ideal sets, twists, cuboids

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

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


Assignment 1

Assignment 2

Assignment 3

Assignment 4

Final project