In mathematics, the upper bound theorem states that
cyclic polytopes have the largest possible number of faces among all
convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
s 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
Theodore Samuel Motzkin (26 March 1908 – 15 December 1970) was an Israeli-American mathematician.
Biography
Motzkin's father Leo Motzkin, a Ukrainian Jew, went to Berlin at the age of thirteen to study mathematics. He pursued university studi ...
, proved in 1970 by
Peter McMullen
Peter McMullen (born 11 May 1942) is a British mathematician, a professor emeritus of mathematics at University College London.
Education and career
McMullen earned bachelor's and master's degrees from Trinity College, Cambridge, and studied at ...
, and strengthened from polytopes to subdivisions of a sphere in 1975 by
Richard P. Stanley
Richard Peter Stanley (born June 23, 1944) is an Emeritus Professor of Mathematics at the Massachusetts Institute of Technology, in Cambridge, Massachusetts. From 2000 to 2010, he was the Norman Levinson Professor of Applied Mathematics. He r ...
.
Cyclic polytopes
The cyclic polytope
may be defined as the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
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
In geometry and polyhedral combinatorics, a -neighborly polytope is a convex polytope in which every set of or fewer vertices forms a face. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an ...
.
Statement
The upper bound theorem states that if
is a simplicial sphere of dimension
with
vertices, then
The difference between
for the dimension of the simplicial sphere, and
for the dimension of the cyclic polytope, comes from the fact that the surface of a
-dimensional polytope (such as the cyclic polytope) is a
-dimensional subdivision of a sphere.
Therefore, the upper bound theorem implies that the number of faces of an arbitrary polytope can never be more than the number of faces of a cyclic or neighborly polytope with the same dimension and number of vertices.
Asymptotically, this implies that there are at most
faces of all dimensions.
The same bounds hold as well for convex polytopes that are not simplicial, as perturbing the vertices of such a polytope (and taking the convex hull of the perturbed vertices) can only increase the number of faces.
History
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 using the notion of a
Stanley–Reisner ring In mathematics, a Stanley–Reisner ring, or face ring, is a quotient of a polynomial algebra over a field by a square-free monomial ideal. Such ideals are described more geometrically in terms of finite simplicial complexes. The Stanley–Reisner ...
and homological methods. For a nice historical account of this theorem see Stanley's article "How the upper bound conjecture was proved".
References
{{reflist
Polyhedral combinatorics