en>Alvin Seville: removing and categorizing

2013-12-30T12:17:17Z

removing and categorizing

New page

In mathematics, the '''upper bound theorem''' states that [[cyclic polytope]]s have the largest possible number of faces among all [[convex polytope]]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]], proved in 1970 by [[Peter McMullen]],<ref>{{citation|title=Lectures on Polytopes|volume=152|series=Graduate Texts in Mathematics|first=Günter M.|last=Ziegler|authorlink=Günter M. Ziegler|publisher=Springer|year=1995|isbn=9780387943657|page=254|url=http://books.google.com/books?id=xd25TXSSUcgC&pg=PA254|quotation=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 to key tools: shellability and ''h''-vectors.}}</ref> and strengthened from polytopes to subdivisions of a sphere in 1975 by [[Richard P. Stanley]].

==Cyclic polytopes==
{{main|Cyclic polytope}}
The cyclic polytope ''Δ''(''n'',''d'') may be defined as the [[convex hull]] of ''n'' [[vertex (geometry)|vertices]] on the [[moment curve]] (''t'', ''t''<sup>2</sup>, ''t''<sup>3</sup>, ...). The precise choice of which ''n'' points on this curve are selected is irrelevant for the combinatorial structure of this polytope.
The number of ''i''-dimensional faces of ''Δ''(''n'',''d'') is given by the formula

: <math> f_i(\Delta(n,d)) = \binom{n}{i+1} \quad \textrm{for} \quad
0 \leq i < \left[\frac{d}{2}\right] </math>

and <math>(f_0,\ldots,f_{[\frac{d}{2}]-1})</math> completely determine <math>(f_{[\frac{d}{2}]},\ldots,f_{d-1})</math> via the [[Dehn–Sommerville equations]]. The same formula for the number of faces holds more generally for any [[neighborly polytope]].

==Statement==
The upper bound theorem states that if ''Δ'' is a simplicial sphere of dimension ''d'' − 1 with ''n'' vertices, then
: <math> f_i(\Delta) \leq f_i(\Delta(n,d)) \quad \textrm{for}\quad i=0,1,\ldots,d-1.</math>
That is, 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 <math>\scriptstyle O(n^{\lfloor d/2\rfloor})</math> 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-vector|''h''-vectors]]:

: <math> h_i(\Delta) \leq \tbinom{n-d+i-1}{i} \quad
\textrm{for} \quad
0 \leq i < \left[\frac{d}{2}\right]. </math>

Victor Klee suggested that the same statement should hold for all simplicial spheres and this was indeed established in 1975 by Stanley <ref>{{cite book |title=Combinatorics and commutative algebra|last=Stanley|first=Richard|authorlink= |year=1996 |publisher=Birkhäuser Boston, Inc.|location= Boston, MA |isbn=0-8176-3836-9 |pages=164}}</ref> using the notion of a [[Stanley–Reisner ring]] and homological methods.

==References==
{{reflist}}

[[Category:Polyhedral combinatorics]]

Rayleigh dissipation function - Revision history

en>Alvin Seville: removing and categorizing