Almost integral polyhedra related to certain combinatorial optimization problems

AbstractThe notion of an almost integral polyhedron is introduced and used to obtain a new proof of the characterization of perfect zero-one matrices which relies only on standard arguments from linear algebra and convexity. The characterization of perfect zero-one matrices in terms of forbidden submatrices is then used to derived the perfect-graph theorem due to Fulkerson and Lovász. Furthermore, a characterization of antiblocking pairs of zero-one matrices by means of a strengthened version of the max-max inequality due to Fulkerson is obtained which entails Lovász's recent characterization of perfect graphs