Purchase Print Copy

 FormatList Price Price
Add to Cart Paperback0.26 pages $20.00 $16.00 20% Web Discount

A geometric theory of "blocking polyhedra" is developed and applied to a number of problems in extremal combinatorics. The basic notion is a variant of the concept of polar polyhedra and exhibits a similar duality. The max-flow min-cut equality and the length-width inequality, valid for paths and cuts in a network, always hold for a blocking pair of polyhedra, and the former of these characterizes the blocking relation. A typical combinatorial application is a new geometric characterization of the permutation matrices as the extreme points of a certain unbounded convex polyhedron. 33 pp. Refs. (Author)

This report is part of the RAND Corporation research memorandum series. The Research Memorandum was a product of the RAND Corporation from 1948 to 1973 that represented working papers meant to report current results of RAND research to appropriate audiences.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.