Zyklisches Polytop

Ein zyklisches Polytop ist ein konvexes Polytop mit Ecken auf der Momentenkurve. Es ist für viele Fragen der kombinatorischen Theorie von Polytopen von großer Bedeutung, unter anderem für das Upper-Bound-Theorem.

Definition

Sei $x\!\,(t)=(t,t^2,...,t^d) \in \R^d$ die Momentenkurve in der Dimension d.

Dann ist das zyklische Polytop $C\!\,(d,n)$ die konvexe Hülle von n Punkten auf der Momentenkurve, wobei n mindestens so groß sein muss wie d+1.

$C(d,n)=\mathrm{conv}\!\,(\{x(t_1),x(t_2),...,x(t_{n})\})$  mit  $\!\,t_1 < t_2 < \cdots < t_{n}$

Es ist auch möglich das zyklische Polytop auf anders definierten Momentenkurven zu definieren.

Beispiele

Im zweidimensionalen ist die Momentenkurve mit der Normalparabel identisch. Jedes Polygon dessen Ecken auf der Normalparabel liegen ist ein zyklisches Polytop.

Eigenschaften

• Zwei gleichdimensionale zyklische Polytope mit der gleichen Eckenanzahl sind kombinatorisch äquivalent. Man kann also von dem zyklischen d-Polytop mit n Ecken sprechen. Diese Eigenschaft folgt aus dem Geradheitskriterium von Gale.
• Das zyklische Polytop ist ein simpliziales Polytop, d.h. jede echte Seite von ihm ist ein Simplex.
• Des Weiteren ist $C\!\,(d,n)$ ein $\lfloor \tfrac{d}{2} \rfloor$-nachbarschaftliches Polytop. Jede konvexe Hülle einer beliebigen Menge von $\lfloor \tfrac{d}{2} \rfloor$ Ecken ist eine Seite des Polytops.
• Die herausragendste Eigenschaft des zyklischen Polytops ist seine "extremalität". Unter allen d-dimensionalen Polytopen mit n Ecken hat $C\!\,(d,n)$ die maximale Anzahl von k-dimensionalen Seiten (k < d). Ein d-Polytop mit n Ecken kann also nicht mehr k-Seiten haben als das entsprechende zyklische Polytop mit n Ecken (Upper-Bound-Theorem).

Literatur

• Branko Grünbaum mit Volker Kaibel, Victor Klee, Günter M. Ziegler: Convex Polytopes. 2. Auflage, Springer 2003, ISBN 0-387-00424-6 (zuerst von Grünbaum 1967).