Tutte Colloquium | Bertrand Guenin, Integral Set Packing versus Integral Set Covering

Abstract: A 0-1 matrix M is perfect if the polyhedron {x ≥ 0 : Mx ≤ 1} is integral. Perfect matrices are closely related to perfect graphs and have several remarkable properties. In particular, perfectness is equivalent to total dual integrality, and perfect matrices admit an excluded-minor characterization.

A 0-1 matrix M is ideal if the polyhedron {x ≥ 0 : Mx ≥ 1} is integral. Unlike perfect matrices, ideal matrices do not correspond to a single well-understood class of combinatorial objects. In this talk, we will explore which of the remarkable properties of perfect matrices have counterparts for ideal matrices. We will discuss what is known, what fails, and some of the intriguing open questions that arise from this comparison.