NOTES ON COMBINATORIAL MATHEMATICS: ANTI-BLOCKING POLYHEDRA
D. R. Fulkerson · 1970
Abstract : A geometric duality theory of anti-blocking pairs of polyhedra is developed and applied to a number of problems in extremal combinatorics. It is shown that anti-blocking pairs are characterized by a min-max equality, the analogue of the max-flow min-cut equality for blocking pairs of polyhedra, or by a max-max inequality, the analogue of the length-width inequality for blocking pairs of polyhedra. A main combinatorial result is that if A, B are (0,1)- matrices defining an anti-blocking pair of polyhedra, then the min-max equality holds for both ordered pairs A, B and B, A in a strong integer form. This theorem bears on a well-known unsolved problem in graph theory, the perfect graph conjecture, and in fact proves what might be called the 'pluperfect' graph theorem.