# 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.

# Descriptors:

# Subject Categories:

- Theoretical Mathematics