Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral combinatorics falls into two distinct areas. Mathematicians in this area study the combinatorics of polytopes; for instance, they seek 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, 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). 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.
Faces and face-counting vectors
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. 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. Note that this definition also includes as faces the empty set and the whole polytope P. If P itself has dimension d, the faces of P with dimension d − 1 are called facets of P and the faces with dimension d − 2 are called ridges. 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 (f0, f1, ..., fd − 1) where fi 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 polytope 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). Configuration matrices include the f-vectors of regular polytopes as diagonal elements. The extended ƒ-vector is formed by concatenating 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, f−1 = 1 counts the empty set as a face, while on the right side, fd = 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 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. 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 (omitting the final 1) as coefficients of a polynomial ƒ(x) = Σfixd − i − 1 (for instance, for the octahedron this gives the polynomial ƒ(x) = x3 + 6x2 + 12x + 8), then the h-vector lists the coefficients of the polynomial h(x) = ƒ(x − 1) (again, for the octahedron, h(x) = x3 + 3x2 + 3x + 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 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. From the fact that each facet of a three-dimensional polyhedron has at least three edges, it follows by double counting that 2e ≥ 3f, and using this inequality to eliminate e and f from Euler's formula leads to the further inequalities e ≤ 3v − 6 and f ≤ 2v − 4. By duality, e ≤ 3f − 6 and v ≤ 2f − 4. It follows from Steinitz's theorem that any 3-dimensional integer vector satisfying these equalities and 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 hk = hd − 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 and 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 polytope 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 ≤ ∑ i = 0 d / 2
… excerpt ends here. Continue reading the full article.
