Accession Number:

AD0702431

Title:

NOTES ON COMBINATORIAL MATHEMATICS: ANTI-BLOCKING POLYHEDRA

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1970-02-01

Pagination or Media Count:

52.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE