NOTES ON COMBINATORIAL MATHEMATICS: ANTI-BLOCKING POLYHEDRA
RAND CORP SANTA MONICA CA
Pagination or Media Count:
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.
- Theoretical Mathematics