Ideal 0, 1 matrices (Q1322011)

We define a \(0, 1\) matrix \(M\) to be ideal if all vertices of the polyhedron \(\{x: Mx\geq 1,\;x\geq 0\}\) have only \(0, 1\) components. We expand the list of known minor minimal nonideal matrices by several hundred. Many of these examples are obtained polyhedrally, by constructing new minimally nonideal matrices from old ones. We present a conjecture that might be viewed as the counterpart for ideal matrices of Berge's Strong Perfect Graph Conjecture. We provide evidence for the conjecture by completely characterizing all minimally nonideal circulants.