Applying Lehman's theorems to packing problems (Q1919808): Difference between revisions

A matrix \(A\) is ideal if the polyhedron \(\{x\in Q^V \mid A \cdot x\geq 1\) and \(x\geq 0\}\) is integral, and perfect if the polyhedron \(\{x\in Q^V \mid A \cdot x\leq 1\) and \(x\geq 0\}\) is integral. The author gives a bijection between superclasses of the classes of ideal and perfect matrices, obtaining new results on packing polyhedra and stable set polytopes of near-bipartite graphs (deletion of any neighbourhood results in a bipartite graph) and some other classes of graphs.