Polyhedral Combinatorics - Faces and Face-counting Vectors

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 (f₀, f₁, ..., f_{d − 1}) where f_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 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). 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, f_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 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) = Σf_ixd − 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.”