Polyhedral combinatorics

Polyhedral combinatorics is a branch of mathematics that studies the problems of counting and describing the faces of convex polyhedra and higher dimensional convex polytopes.

A key question in polyhedral combinatorics is to find inequalities that describe the relations between the numbers of vertices, edges, and faces of higher dimensions in arbitrary polytopes or in certain important subclasses of polytopes. Researchers in this area also seek precise descriptions of the faces of certain specific polytopes arising from integer programming problems, and study other combinatorial properties of polytopes such as their connectivity and diameter (number of steps needed to reach any vertex from any other vertex).

Faces and face-counting vectors

The face lattice of a convex polytope.

A face of a convex polytope P may be defined as the intersection of P and a closed halfspace H such that the boundary of H contains no interior point of P. Equivalently, a face is the intersection of P with the affine hull of a subset of its vertices. The dimension of a face is the dimension of this hull. The 0-dimensional faces are the vertices themselves, and the 1-dimensional faces (called edges) are line segments connecting pairs of vertices. If P itself has dimension d, the faces of P with dimension d − 1 are called facets of P. The faces of P may be partially ordered by inclusion, forming a face lattice that has as its top element P itself and as its bottom element the empty set.

A key tool in polyhedral combinatorics is the ƒ-vector of a polytope, the vector (n₀, n₁, ...) where n_i is the number of i-dimensional features of the polytope. For instance, a cube has eight vertices, twelve edges, and six facets, so its ƒ-vector is (8,12,6). The dual polyhedron has a ƒ-vector with the same numbers in the reverse order; thus, for instance, the regular octahedron, the dual to a cube, has the ƒ-vector (6,12,8). The extended ƒ-vector is formed by setting including the number one at each end of the ƒ-vector, counting the number of objects at all levels of the face lattice; on the left side of the vector, n_-1 = 1 counts the empty set as a face, while on the right side, n_d = 1 counts P itself. For the cube the extended ƒ-vector is (1,8,12,6,1) and for the octahedron it is (1,6,12,8,1). Although the vectors for these simple polyhedra are unimodal (they increase to a maximum and then decrease), there are higher dimensional polytopes for which this is not true.

For simplicial polytopes (polytopes in which every facet is a simplex), it is often convenient to transform these vectors, producing a different vector called the h-vector. If we interpret the terms of the ƒ-vector as coefficients of a polynomial ƒ(x) = Σn_ix^d − i (for instance, for the cube this gives the polynomial ƒ(x) = x⁴ + 8x³ + 12x² + 6x + 1), then the h-vector lists the coefficients of the polynomial ƒ(x − 1). 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.”

Equalities and inequalities

The most important relation among the coefficients of the ƒ-vector of a polyhedron is Euler's formula Σ(-1)ⁱn_i = 0, where the terms of the sum range over the coefficients of the extended ƒ-vector. In three dimensions, omitting the two 1's at the left and right ends of the extended ƒ-vector (1, v, e, f, 1) transforms this identity into the more familiar form v − e + f = 2. From the fact that each facet of a polyhedron has at least three edges, it follows that 2e ≤ 3f, and using this inequality to eliminate e and f from Euler's formula leads to the further inequalities e ≤ 2v − 4 and f ≤ 3v − 6. By duality, e ≤ 2f − 4 and v ≤ 3f − 6. Any 3-dimensional integer vector satisfying these inequalities is the ƒ-vector of a convex polyhedron.

In higher dimensions, other relations among the numbers of faces of a polytope become important as well, including the Dehn–Sommerville equations which, expressed in terms of h-vectors of simplicial polytopes, take the simple form h_k = h_d − k for all k. The instance of these equations with k = 0 is equivalent to Euler's formula but for d > 3 the other instances of these equations are linearly independent of each other constrain the h-vectors (and therefore also the ƒ-vectors) in additional ways.

Another important inequality on polytope face counts is given by the upper bound theorem, first proven by McMullen (1970), which states that a d-dimensional polytopes with n vertices can have at most as many faces of any other dimension as a neighborly polytope with the same number of vertices:

$f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {d-i}{k-i}}+{\binom {i}{k-d+i}}\right){\binom {n-d-1+i}{i}},$

where the asterisk means that the final term of the sum should be halved when d is even. Asymptotically, this implies that there are at most $\scriptstyle O(n^{\lfloor d/2\rfloor })$ faces of all dimensions.

Even in four dimensions, the set of possible ƒ-vectors of convex polytopes does not form a convex subset of the four-dimensional integer lattice, and much remains unknown about the possible values of these vectors.

Graph-theoretic properties

Along with investigating the numbers of faces of polytopes, researchers have studied other combinatorial properties of them, such as descriptions of the graphs obtained from the vertices and edges of polytopes (their 1-skeleta).

Balinski's theorem states that the graph obtained in this way from any d-dimensional convex polytope is d-vertex-connected. In the case of three-dimensional polyhedra, this property and planarity may be used to exactly characterize the graphs of polyhedra: Steinitz' theorem states that G is the skeleton of a three-dimensional polyhedron if and only if G is a 3-vertex-connected planar graph.

In the context of the simplex method for linear programming, it is important to understand the diameter of a polytope, the minimum number of edges needed to reach any vertex from any other vertex. The simplex method finds an optimal vertex of a polytope describing a system of linear inequalities by following a path of this type in the polytope, and the diameter provides a lower bound on the number of steps this method requires. The Hirsch conjecture, still unproven, is that a d-dimensional polytope with n facets has diameter at most n − d.

References

• Balinski, Michel L. (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics, 11: 431–434.

• Cook, William; Seymour, Paul D. (1989), Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, ISBN 9780821865910.

• Höppner, Andrea; Ziegler, Günter M. (2000), A census of flag-vectors of 4-polytopes. In Kalai & Ziegler (2000), pp. 105–110.

• Kalai, Gil; Ziegler, Günter M. (2000), Polytopes: Combinatorics and Computation, DMV Seminar, vol. 29, Birkhäuser, ISBN 9783764363512.

• McMullen, Peter (1970), "The maximum numbers of faces of a convex polytope", Mathematika, 17: 179–184.

• Schrijver, Alexander (1987), Polyhedral Combinatorics, Centrum voor Wiskunde en Informatica.

• Steinitz, Ernst (1906), "Über die Eulerschen Polyederrelationen", Archiv für Mathematik und Physik, 11: 86–88.

• Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, ISBN 0-387-94365-X.