Polyhedral combinatorics

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.

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

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". [harvtxt|Ziegler|1995, p. 51.] 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, [harvtxt|Ziegler|1995, pp. 245–246.] 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 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, "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 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. [harvtxt|Ziegler|1995, p. 272.]

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") = Σ"n_ix"^{"d" − "i" − 1} (for instance, for the octahedron this gives the polynomial ƒ("x") = "x"³ + 6"x"² + 12"x" + 8), then the "h"-vector lists the coefficients of the polynomial "h"("x") = ƒ("x" − 1) (again, for the octahedron, "h"("x") = "x"³ + 3"x"² + 3"x" + 1).harvtxt|Ziegler|1995, pp. 246–253.] 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)^"i""n_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 polyhedron has at least three edges, it follows by double counting that 2"e" ≤ 3"f", and using this inequality to eliminate "e" and "f" from Euler's formula leads to the further inequalities "e" ≤ 2"v" − 4 and "f" ≤ 3"v" − 6. By duality, "e" ≤ 2"f" − 4 and "v" ≤ 3"f" − 6. Any 3-dimensional integer vector satisfying these equalities and inequalities is the ƒ-vector of a convex polyhedron. [harvtxt|Steinitz|1906.]

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 theorem, first proven by harvtxt|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::where the asterisk means that the final term of the sum should be halved when "d" is even. [harvtxt|Ziegler|1995, pp. 254–258.] Asymptotically, this implies that there are at most $scriptstyle\; O(n^\{lfloor\; d/2\; floor\})$ 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. [harvtxt|Höppner|Ziegler|2000.]

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. [harvtxt|Balinski|1961; harvtxt|Ziegler|1995, pp. 95–96.] 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. [harvtxt|Ziegler|1995, pp. 103–126.]

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 by a path from any other vertex. 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. Thus, 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".

Facets of 0-1 polytopes

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. Often, these problems have solutions that can be described by binary vectors, and the corresponding polytopes have vertex coordinates that are all zero or one.

As an example, consider the Birkhoff polytope, the set of "n" × "n" matrices that can be formed from convex combinations of permutation matrices. 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. First, for each matrix cell, there is a constraint that this cell has a non-negative value. And second, for each row or column of the matrix, there is a constraint that the sum of the cells in that row or column equal one. The row and column constraints define a linear subspace of dimension "n"² − 2"n" + 1 in which the Birkhoff polytope lies, and the non-negativity constraints define facets of the Birkhoff polytope within that subspace.

However, the Birkhoff polytope is unusual in that a complete description of its facets is available. For many other 0-1 polytopes, there are exponentially many or superexponentially many facets, and only partial descriptions of their facets are available. [harvtxt|Ziegler|2000.]

Notes

References

*citation
last = Balinski | first = Michel L.
journal = Pacific Journal of Mathematics
pages = 431–434
title = On the graph structure of convex polyhedra in n-space
volume = 11
year = 1961.

*citation
last1 = Cook | first1 = William
last2 = Seymour | first2 = Paul D. | author2-link = Paul Seymour (mathematician)
isbn = 9780821865910
publisher = American Mathematical Society
series = DIMACS Series in Discrete Mathematics and Theoretical Computer Science
title = Polyhedral Combinatorics
year = 1989.

*citation
last1 = Höppner | first1 = Andrea
last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler
title = A census of flag-vectors of 4-polytopes
year = 2000. In harvtxt|Kalai|Ziegler|2000, pp. 105–110.

*citation
last1 = Kalai | first1 = Gil | author1-link = Gil Kalai
last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler
isbn = 9783764363512
publisher = Birkhäuser
series = DMV Seminar
title = Polytopes: Combinatorics and Computation
volume = 29
year = 2000.

*citation
last = McMullen | first = Peter
journal = Mathematika
pages = 179–184
title = The maximum numbers of faces of a convex polytope
volume = 17
year = 1970.

*citation
last = Schrijver | first = Alexander
publisher = Centrum voor Wiskunde en Informatica
title = Polyhedral Combinatorics
year = 1987.

*citation
last = Steinitz | first = Ernst | author-link = Ernst Steinitz
journal = Archiv für Mathematik und Physik
pages = 86–88
title = Über die Eulerschen Polyederrelationen
volume = 11
year = 1906.

*citation
last = Ziegler | first = Günter M. | author-link = Günter M. Ziegler
isbn = 0-387-94365-X
publisher = Springer-Verlag
series = Graduate Texts in Mathematics
title = Lectures on Polytopes
volume = 152
year = 1995.

*citation
last = Ziegler | first = Günter M. | author-link = Günter M. Ziegler
title = Lectures on 0-1 polytopes
year = 2000. In harvtxt|Kalai|Ziegler|2000.

External links

*citation
url=http://gilkalai.wordpress.com/2008/05/07/five-open-problems-regarding-convex-polytopes/
title = Five Open Problems Regarding Convex Polytopes
first = Gil | last = Kalai | year = 2008.