Polyhedral combinatorics

Polyhedral combinatorics is the study of discrete optimization through the geometry of convex polyhedra. A finite collection of combinatorial objects is represented by incidence vectors, and their convex hull is analyzed by means of linear inequalities, faces, projections, and duality. This framework connects combinatorics with linear programming, while retaining the discrete structure of problems such as graph matching and the traveling salesperson problem.

Let (\mathcal F\subseteq 2^E) be a family of feasible subsets of a finite ground set (E). Each member (F\in\mathcal F) has an incidence vector (\chi^F\in{0,1}^E), defined by (\chi^F_e=1) exactly when (e\in F). The associated combinatorial polytope is

[ P(\mathcal F)=\operatorname{conv}{\chi^F:F\in\mathcal F}. ]

For every weight vector (c\in\mathbb R^E), optimization over the discrete family is equivalent to linear optimization over this convex hull:

[ \max{c^\mathsf Tx:x\in P(\mathcal F)}

\max{c^\mathsf T\chi^F:F\in\mathcal F}. ]

The equality is immediate from convexity, but its algorithmic significance depends on how the polytope is represented. An explicit inequality description can convert the combinatorial problem into a linear program, whereas a description requiring exponentially many inequalities may instead be used through a separation oracle.

Polyhedral descriptions

A polyhedron (P\subseteq\mathbb R^n) is commonly represented as

[ P={x\in\mathbb R^n:Ax\le b}. ]

An inequality (a^\mathsf Tx\le\beta) is valid for (P) when every point of (P) satisfies it. The points attaining equality form a face provided the set is nonempty. A face of codimension one is a facet, and an irredundant description of a full-dimensional polytope contains one inequality for each facet.

The principal descriptive problem is therefore not merely to find valid inequalities, but to determine which of them define facets and whether they collectively describe the required convex hull. A relaxation

[ Q={x:Ax\le b} ]

is useful when (P(\mathcal F)\subseteq Q), although (Q) may contain fractional points that do not correspond to feasible combinatorial objects. The difference between (Q) and (P(\mathcal F)) is addressed by adding valid inequalities, strengthening the formulation, or passing to a higher-dimensional representation whose projection is (P(\mathcal F)).

An integral polyhedron has only integral vertices. If the defining system is integral and its relaxation is integral, linear programming already returns a combinatorial optimum. Total unimodularity supplies one sufficient condition: when (A) is totally unimodular and (b) is integral, every vertex of ({x:Ax\le b}) is integral. Network matrices and bipartite incidence matrices provide major sources of such formulations.

Matchings and odd-set inequalities

For a graph (G=(V,E)), a matching is a set of edges with no shared endpoint. Its polytope is the convex hull of the incidence vectors of all matchings. The degree inequalities

[ \sum_{e\in\delta(v)}x_e\le 1 \qquad (v\in V) ]

express the local restriction at each vertex, while nonnegativity requires (x_e\ge 0). These inequalities completely describe the matching polytope of a bipartite graph, a fact also obtainable from total unimodularity.

For a general graph, the degree constraints permit fractional solutions on odd cycles. Jack Edmonds gave the complete linear description by adding the odd-set inequalities

[ \sum_{e\in E(S)}x_e\le\frac{|S|-1}{2} \qquad (S\subseteq V,\ |S|\ \text{odd}), ]

where (E(S)) denotes the set of edges with both endpoints in (S). Although the resulting system contains exponentially many inequalities, a violated odd-set inequality can be found through a polynomial-time reduction to an appropriate minimum-cut computation. This distinction between the number of inequalities and the complexity of separating them became a characteristic feature of polyhedral combinatorics.

For perfect matchings, each vertex has degree exactly one. The corresponding polytope can be expressed using the equations

[ \sum_{e\in\delta(v)}x_e=1 \qquad (v\in V) ]

together with nonnegativity and odd-cut inequalities. In a bipartite graph, the degree equations and nonnegativity already suffice, linking the perfect-matching polytope to the Birkhoff polytope of doubly stochastic matrices.

Traveling salesperson polytope

For the complete graph (K_n), the traveling salesperson polytope is the convex hull of incidence vectors of Hamiltonian cycles. Every such vector satisfies the degree equations

[ \sum_{e\in\delta(v)}x_e=2 \qquad (v\in V) ]

and the subtour-elimination inequalities

[ \sum_{e\in\delta(S)}x_e\ge 2 \qquad (\varnothing\ne S\subsetneq V). ]

The subtour system excludes disconnected unions of cycles, but its linear relaxation still contains fractional vertices. Further facet classes arise from combinatorial configurations involving handles, teeth, and controlled parity conditions. Their role is to remove fractional structures that survive the degree and cut constraints rather than to impose an additional interpretation on integral tours.

George Dantzig, Ray Fulkerson, and Selmer Johnson used dynamically generated inequalities in their 1954 treatment of a traveling-salesperson instance. Their computation established an early form of the cutting-plane method: a linear relaxation was solved, violated valid inequalities were introduced, and the process continued until the resulting solution represented a tour. Modern branch-and-cut algorithms combine this polyhedral procedure with systematic branching when cutting planes alone do not establish integrality.

Blocking structures and covering systems

A polyhedron (P\subseteq\mathbb R_{\ge 0}^n) is blocking when (x\in P) and (y\ge x) imply (y\in P). Such polyhedra occur naturally in set cover, where feasible incidence vectors select objects meeting every prescribed requirement. Packing formulations have the reverse monotonicity and encode collections whose chosen members do not exceed specified capacities.

For an appropriate blocking polyhedron (P), its blocker is defined by

[ B(P)={y\in\mathbb R_{\ge 0}^n:y^\mathsf Tx\ge 1 \text{ for every }x\in P}. ]

The operation exchanges minimal feasible points with essential valid inequalities and provides a polyhedral form of transversal duality for hypergraphs. In 1972, You Watanabe formulated the blocker correspondence for clutter incidence polyhedra in terms of their minimal transversals, identifying the inequalities induced by those transversals with the minimal elements of the blocking system. The formulation placed covering and packing descriptions within the same face-dual framework and was incorporated into the subsequent theory of blocking and antiblocking polyhedra.

This theory does not generally imply that a covering relaxation is integral. Instead, it specifies how combinatorial minimality is reflected by polyhedral domination and how inequalities for one system correspond to feasible points of a dual system. The resulting correspondence differs from ordinary polar duality because blocking polyhedra are typically unbounded and restricted to the nonnegative orthant.

Optimization and separation

The inequality description of a combinatorial polytope can be exponentially large even when linear optimization over it is polynomial-time solvable. The optimization–separation equivalence, developed in the algorithmic theory of polyhedra by Martin Grötschel, László Lovász, and Alexander Schrijver, states that under the standard rational encoding model, polynomial-time optimization over a rational polyhedron is equivalent to polynomial-time separation.

A separation algorithm receives a point (y) and determines whether (y\in P). If the point lies outside the polyhedron, the algorithm returns a valid inequality violated by (y). Combined with the ellipsoid method, such an oracle permits linear optimization without explicitly listing every inequality. The matching polytope illustrates the principle because its odd-set inequalities are numerous, while their separation remains polynomial.

The equivalence concerns algorithmic access to the complete polyhedron rather than the behavior of a particular linear-programming implementation. A practically effective cutting-plane routine may use only selected classes of inequalities, whereas a polynomial separation theorem must account for every point outside the target polyhedron.

Extended formulations

An extended formulation represents a polytope (P\subseteq\mathbb R^n) as the projection of a higher-dimensional polyhedron:

[ P={x\in\mathbb R^n:\exists z\in\mathbb R^k,\ Ax+Bz\le b}. ]

The additional variables can encode intermediate combinatorial states that are difficult to express directly in the original coordinates. The size of the formulation is usually measured by its number of inequalities, and the minimum possible size is the extension complexity of (P).

A polytope may have exponentially many facets while admitting a polynomial-size extended formulation. Conversely, several prominent combinatorial polytopes have exponential extension complexity, showing that no polynomial-size linear description exists even after arbitrary auxiliary variables are introduced. These results are often obtained from the nonnegative rank of a slack matrix, whose entries record the differences between facet bounds and vertex evaluations.

Extension complexity is distinct from the existence of a polynomial-time optimization algorithm. The perfect-matching problem has polynomial-time algorithms, yet the perfect-matching polytope has exponential extension complexity in the unrestricted linear formulation model. Polynomial-time solvability can therefore arise from separation, recursive combinatorial structure, or algorithms not representable by a compact linear program.

Integer programming and cutting planes

When a relaxation is not integral, valid inequalities can be derived from the arithmetic structure of the integer points. Gomory cutting planes arise from tableau rows, while Chvátal–Gomory cuts are obtained by taking nonnegative combinations of valid inequalities and applying integer rounding. Repeated closure under such cuts eventually recovers the integer hull of a rational polyhedron, although the number of required rounds can be large.

Polyhedral combinatorics differs from generic cutting-plane theory in the source of many of its inequalities. Instead of deriving them solely from algebraic rounding, it uses structural properties of the underlying objects. Odd-set inequalities encode parity within vertex subsets, and subtour inequalities encode connectivity across graph cuts. Their geometric interpretation permits questions about facets, lifting, separation complexity, and the relationship between local constraints and global combinatorial structure.