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 theorem, 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

.^[1]

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.^[1]

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

Gale evenness condition

The Gale evenness condition^[2] 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)$ .

Neighborliness

Cyclic polytopes are examples of neighborly polytopes, in that every set of at most d/2 vertices forms a face. They were the first neighborly polytopes known, and Theodore Motzkin conjectured that all neighborly polytopes are combinatorially equivalent to cyclic polytopes, but this is now known to be false.^[3]^[4]

Number of faces

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

f_i(\Delta(n,d)) = \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.

Upper bound theorem

Main article: Upper bound theorem

The upper bound theorem states that cyclic polytopes have the maximum possible number of faces for a given dimension and number of vertices: 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 Theodore Motzkin in 1957 and proved by Peter McMullen in 1970. Victor Klee suggested that the same statement should hold for all simplicial spheres and this was indeed established in 1975 by Richard P. Stanley^[5] using the notion of a Stanley–Reisner ring and homological methods.

References

1 2 3 Miller, Ezra; Sturmfels, Bernd (2005). Combinatorial commutative algebra. Graduate Texts in Mathematics 227. New York, NY: Springer-Verlag. p. 119. ISBN 0-387-23707-0. Zbl 1090.13001.
↑ Ziegler, Günter (1994). Lectures on Polytopes. Springer. p. 14. ISBN 0-387-94365-X.
↑ Gale, David (1963), "Neighborly and cyclic polytopes", in Klee, Victor, Convexity, Seattle, 1961, Symposia in Pure Mathematics 7, American Mathematical Society, pp. 225–233, ISBN 978-0-8218-1407-9 .
↑ Shermer, Ido (1982), "Neighborly polytopes", Israel Journal of Mathematics 43 (4): 291–311, doi:10.1007/BF02761235 .
↑ Stanley, Richard (1996). Combinatorics and commutative algebra. Boston, MA: Birkhäuser Boston, Inc. p. 164. ISBN 0-8176-3836-9.

This article is issued from Wikipedia - version of the Monday, May 05, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.