Polyhedral Combinatorics - Equalities and Inequalities

Equalities and Inequalities

The most important relation among the coefficients of the ƒ-vector of a polytope is Euler's formula Σ(−1)if_i = 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 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 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 Conjecture, 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:

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 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.