The ACO Seminar (2018–2019)

A $0,1$ matrix $M$ is *ideal* if the linear system $Mx \geq 1$, $x \geq 0$ constitutes an integral polyhedron. A classic result of Hoffman (1974) and Edmonds and Giles (1977) proves that if this linear system is totally dual integral, then $M$ is ideal. The converse does not hold in general. However, a conjecture by Cornuejols, Guenin and Margot (2000) predicts that if $M$ has no *intersecting restriction*, then the converse should hold.

I will discuss this conjecture, provide a "good" characterization of matrices without an intersecting restriction, and discuss a surprising consequence of the techniques developed. This talk is based on joint works with Gerard Cornuejols and Dabeen Lee.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.