Geradheitskriterium von Gale

Das Geradheitskriterium von Gale beschreibt eine Bedingung an die Eckenmengen von Facetten eines zyklischen Polytops. Es geht auf den Mathematiker David Gale zurück.

Eine Konsequenz des Geradheitskriteriums von Gale ist es, dass zwei gleichdimensionale zyklische Polytope mit gleicher Eckenanzahl kombinatorisch äquivalent sind. Man also von dem zyklischen d-Polytop mit n Ecken sprechen kann.

Definition

Sei $V\!\,$ die Eckenmenge eines zyklischen Polytops $C(d,n)\!\,$ und sei $V_d\!\,$ eine Menge aus d Ecken des Polytops.

Die konvexe Hülle von $V_d\!\,$ ist dann genau dann eine Facette wenn jedes Paar aus zwei Ecken aus $V \setminus V_d\!\,$ von einer geraden Anzahl von Ecken aus $V_d\!\,$ auf der Momentenkurve getrennt wird.

Beispiel

$C(3,6)\!\,$ ist ein zyklisches Polytop in der Dimension 3 mit 6 Ecken. Seine Ecken sind nach ihrer Reihenfolge auf der Momentenkurve durchnummeriert. $V_3\!\, =\{0,3,4\}$ ist eine Menge bestehend aus drei Ecken des Polytops.

$V \setminus V_3\!\,$ besteht aus $\{1,2,5\}\!\,$.

• Die Ecken 1 und 2 werden von 0 Ecken auf der Momentenkurve getrennt.
• Die Ecken 1 und 5 werden von den zwei Ecken 3 und 4 auf der Momentenkurve getrennt.
• Die Ecken 2 und 5 werden von den zwei Ecken 3 und 4 auf der Momentenkurve getrennt.

$\mathrm{conv}(V_3)\!\,$ ist damit eine Facette von $C(3,6)\!\,$.

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).