Cyclic polytope

In mathematics, a cyclic polytope, denoted C(n,d), is a convex polytope formed as a convex hull of n distinct points on a rational normal curve in R^d, where n is greater than d. These polytopes were studied by Constantin Carathéodory, David Gale, Theodore Motzkin, Victor Klee, and others. They play an important role in polyhedral combinatorics: according to the Upper Bound Conjecture, proved by Peter McMullen and Richard Stanley, the boundary Δ(n,d) of the cyclic polytope C(n,d) maximizes the number f_i of i-dimensional faces among all simplicial spheres of dimension d − 1 with n vertices.

Definition

The moment curve in $\mathbb{R}^d$ is defined by

$\mathbf{x}:\mathbb{R} \rightarrow \mathbb{R}^d, \mathbf{x}(t) := \begin{bmatrix}t\,t^2\,\ldots\,t^d\end{bmatrix}^T$.

The d-dimensional cyclic polytope with n vertices is the convex hull

$C(n,d) := \mathbf{conv}\{\mathbf{x}(t_1),\mathbf{x}(t_2),\ldots,\mathbf{x}(t_n) \}$

of $n > d \ge 2$ distinct points $\mathbf{x}(t_i)$ with $t_1 < t_2 < \ldots < t_n$ on the moment curve.

The combinatorial structure of this polytope is independent of the points chosen, and the resulting polytope has dimension d and n vertices. Its boundary is a (d − 1)-dimensional simplicial polytope denoted Δ(n,d).

Gale evenness condition

The Gale evenness condition ^[1] provides a necessary and sufficient condition to determine a facet on a cyclic polytope.

Let $T := \{t_1,t_2,\ldots,t_n\}$. Then, a d-subset $T_d \subseteq T$ forms a facet of C(n,d) iff any two elements in $T \setminus T_d$ are separated by an even number of elements from T_d in the sequence $(t_1,t_2,\ldots,t_n)$.

The upper bound conjecture

The number of i-dimensional faces of Δ(n,d) is given by the formula

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

and $(f_0,\ldots,f_{[\frac{d}{2}]-1})$ completely determine $(f_{[\frac{d}{2}]},\ldots,f_{d-1})$ via the Dehn–Sommerville equations.

The Upper Bound Conjecture states that if Δ is a simplicial sphere of dimension d − 1 with n vertices , then

$f_i(\Delta) \leq f_i(\Delta(n,d)) \quad \textrm{for}\quad i=0,1,\ldots,d-1.$

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:

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

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

See also

• Combinatorial commutative algebra

References

1. ^ Ziegler, Günter (1994). Lectures on Polytopes. Springer. pp. 14. ISBN 0-387-94365-X. 
2. ^ Stanley, Richard (1996). Combinatorics and commutative algebra. Boston, MA: Birkhäuser Boston, Inc.. pp. 164. ISBN 0-8176-3836-9.