Upper bound theorem
In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics.
Originally known as the upper bound conjecture, this statement was formulated by Theodore Motzkin, proved in 1970 by Peter McMullen,[1] and strengthened from polytopes to subdivisions of a sphere in 1975 by Richard P. Stanley.
Cyclic polytopes[edit]
The cyclic polytope may be defined as the convex hull of vertices on the moment curve, the set of -dimensional points with coordinates . The precise choice of which points on this curve are selected is irrelevant for the combinatorial structure of this polytope. The number of -dimensional faces of is given by the formula
and completely determine via the Dehn–Sommerville equations. The same formula for the number of faces holds more generally for any neighborly polytope.
Statement[edit]
The upper bound theorem states that if is a simplicial sphere of dimension with vertices, then
History[edit]
The upper bound conjecture for simplicial polytopes was proposed by Motzkin in 1957 and proved by McMullen in 1970. A key ingredient in his proof was the following reformulation in terms of h-vectors:
Victor Klee suggested that the same statement should hold for all simplicial spheres and this was indeed established in 1975 by Stanley[2] using the notion of a Stanley–Reisner ring and homological methods. For a nice historical account of this theorem see Stanley's article "How the upper bound conjecture was proved".[3]
References[edit]
- ^ Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer, p. 254, ISBN 9780387943657,
Finally, in 1970 McMullen gave a complete proof of the upper-bound conjecture – since then it has been known as the upper bound theorem. McMullen's proof is amazingly simple and elegant, combining two key tools: shellability and h-vectors.
- ^ Stanley, Richard (1996). Combinatorics and Commutative Algebra. Birkhäuser Boston. p. 164. ISBN 0-8176-3836-9.
- ^ Stanley, Richard (2014). "How the upper bound conjecture was proved". Annals of Combinatorics. 18 (3): 533–539. CiteSeerX 10.1.1.416.5481. doi:10.1007/s00026-014-0238-5. S2CID 253585250.