Anti-blocking polyhedra

Abstract

A theory parallel to that for blocking pairs of polyhedra is developed for anti-blocking pairs of polyhedra, and certain combinatorial results and problems are discussed in this framework. Blocking pairs of polyhedra are intimately related to maximum packing problems, anti-blocking pairs to minimum covering problems. Let B = {x ∈ R+n | Ax ≤ 1}, where A is a non-negative matrix and 1 = (1,…, 1). The anti-blocker of the convex polyhedron B is defined to be the convex polyhedron B = {x ∈ R+n | x · B ≤ 1}. It is shown that B = B and a method is described for finding a non-negative matrix B such that B={x ∈ R+itn | Bx ≤ 1}. In particular, if A is the incidence matrix of a family of subsets of {1,…, n} having the property that each subset of a member of the family is again a member of the family, a method is described for finding the facets of the convex hull of the rows of A. It is shown that anti-blocking pairs are characterized by a min-max equality, the analog of the max-flow min-cut equality for blocking pairs, or by a max-max inequality, the analog of the length-width inequality for blocking pairs. Finally, the theory of anti-blocking pairs is applied to certain problems in extremal combinatorics. A main result is the following. If A and B are an anti-blocking pair of (0, 1)-matrices, then the min-max equality holds strongly for both ordered pairs A, B and B, A, i.e., both covering problems yA ≥ w, y ≥ 0, min 1 · y, and yB ≥ w, y ≥ 0, min 1 · y, have integer solutions y for all integer vectors w. Conversely, if A is a (0, 1)-matrix with anti-blocker B, and if the min-max equality holds strongly for A, B, then all essential rows of B are (0, 1)-vectors. This theorem bears on the perfect graph conjecture, and in fact proves a closely related theorem, which we call the pluperfect graph theorem.