Accession Number:

AD0679986

Title:

BLOCKING POLYHEDRA

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

• Fulkerson, D. R.

Report Date:

1968-12-01

Pagination or Media Count:

34.0

Abstract:

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.

Descriptors:

• *COMBINATORIAL ANALYSIS
• MATRICES(MATHEMATICS)
• NETWORKS
• PROBABILITY
• THEOREMS
• TOPOLOGY

Subject Categories:

• Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE