Polyhedral combinatorics

Additionally, many computer scientists use the phrase “polyhedral combinatorics” to describe research into precise descriptions of the faces of certain specific polytopes (especially 0-1 polytopes, whose vertices are subsets of a hypercube) arising from integer programming problems.

Although the vectors for these example polyhedra are unimodal (the coefficients, taken in left to right order, increase to a maximum and then decrease), there are higher-dimensional polytopes for which this is not true.

[4] As Ziegler writes, “for various problems about simplicial polytopes, h-vectors are a much more convenient and concise way to encode the information about the face numbers than ƒ-vectors.” The most important relation among the coefficients of the ƒ-vector of a polytope is Euler's formula Σ(−1)ifi = 0, where the terms of the sum range over the coefficients of the extended ƒ-vector.

In three dimensions, moving the two 1's at the left and right ends of the extended ƒ-vector (1, v, e, f, 1) to the right hand side of the equation transforms this identity into the more familiar form v − e + f = 2.

It follows from Steinitz's theorem that any 3-dimensional integer vector satisfying these equalities and inequalities is the ƒ-vector of a convex polyhedron.

Balinski's theorem states that the graph obtained in this way from any d-dimensional convex polytope is d-vertex-connected.

[9] A theorem of Blind & Mani-Levitska (1987) (previously conjectured by Micha Perles) states that one can reconstruct the face structure of a simple polytope from its graph.

However, testing whether a given graph or lattice can be realized as the face lattice of a simple polytope is equivalent (by polarity) to realization of simplicial polytopes, which was shown to be complete for the existential theory of the reals by Adiprasito & Padrol (2017).

The system of linear inequalities of a linear program define facets of a polytope representing all feasible solutions to the program, and the simplex method finds the optimal solution by following a path in this polytope.

The Hirsch conjecture, now disproved, suggested a strong (linear) bound on how large the diameter of a polytope with fixed dimension

) upper bounds on their diameter are known,[11] as well as proofs of the Hirsch conjecture for special classes of polytopes.

[13] It is important in the context of cutting-plane methods for integer programming to be able to describe accurately the facets of polytopes that have vertices corresponding to the solutions of combinatorial optimization problems.

Equivalently, its vertices can be thought of as describing all perfect matchings in a complete bipartite graph, and a linear optimization problem on this polytope can be interpreted as a bipartite minimum weight perfect matching problem.

The Birkhoff–von Neumann theorem states that this polytope can be described by two types of linear inequality or equality.