Polyedrische Kombinatorik

Gegenstand und Grundbegriffe

Die polyedrische Kombinatorik ist ein Teilgebiet der Kombinatorik und der diskreten Geometrie. Sie untersucht konvexe Polyeder sowie konvexe Polytope höherer Dimension. Im Mittelpunkt stehen die Anzahl und die genaue Beschreibung ihrer Seitenflächen sowie Beziehungen zwischen Ecken, Kanten und Facetten. Weitere untersuchte Eigenschaften sind der Zusammenhang und der Durchmesser, also die kleinste Anzahl von Schritten, die nötig ist, um von einer Ecke aus eine beliebige andere Ecke zu erreichen.

Eine Seitenfläche eines konvexen Polytops P entsteht als Schnitt von P mit einem geschlossenen Halbraum H, dessen Rand keinen inneren Punkt von P enthält. Ihre Dimension ist die Dimension ihrer Hülle. 0-dimensionale Seitenflächen heißen Ecken, 1-dimensionale Seitenflächen heißen Kanten. Nach dieser Definition zählen auch die leere Menge und P selbst als Seitenflächen. Ist P d-dimensional, heißen seine Seitenflächen der Dimension d−1 Facetten.

Die Seitenflächen lassen sich durch Inklusion partiell ordnen: Im zugehörigen Ordnungsdiagramm steht das gesamte Polytop P oben und die leere Menge unten.

Vektoren zur Zählung der Seitenflächen

Der f-Vektor (f₀, f₁, …, f_{d−1}) eines d-dimensionalen Polytops gibt an, wie viele Seitenflächen jeder Dimension vorkommen; fᵢ ist die Anzahl der i-dimensionalen Seitenflächen. Ein dreidimensionaler Würfel besitzt 8 Ecken, 12 Kanten und 6 Facetten und hat daher den f-Vektor (8, 12, 6). Beim dualen Polytop erscheinen dieselben Zahlen in umgekehrter Reihenfolge. Das zum Würfel duale Oktaeder hat somit den f-Vektor (6, 12, 8).

Der erweiterte f-Vektor (f_{−1}, f₀, f₁, …, f_{d−1}, f_d) berücksichtigt alle Ebenen des Ordnungsdiagramms. Dabei gilt f_{−1}=1 für die leere Menge und f_d=1 für P selbst. Man erhält ihn, indem man dem gewöhnlichen f-Vektor vorne und hinten jeweils eine 1 hinzufügt. Für den Würfel lautet er (1, 8, 12, 6, 1), für das Oktaeder (1, 6, 12, 8, 1). Beide Vektoren sind unimodal: Ihre Werte steigen zunächst bis zu einem Maximum und fallen danach wieder. In höheren Dimensionen gibt es jedoch Polytope, deren f-Vektoren nicht unimodal sind.

Bei simplizialen Polytopen, deren sämtliche Facetten Simplizes sind, wird der f-Vektor häufig in einen h-Vektor umgewandelt. Dazu verwendet man die Einträge des erweiterten f-Vektors ohne die letzte 1 als Koeffizienten von f(x)=Σᵢ fᵢx^{d−i−1} und definiert h(x)=f(x−1). Der h-Vektor besteht aus den Koeffizienten von h(x). Für das Oktaeder gilt f(x)=x³+6x²+12x+8 und h(x)=f(x−1)=x³+3x²+3x+1. Sein h-Vektor ist daher (1, 3, 3, 1).

Beziehungen und Grenzen

Der wichtigste allgemeine Zusammenhang zwischen den Einträgen des erweiterten f-Vektors ist die Euler-Charakteristik Σ(−1)ⁱfᵢ=0. Für den erweiterten f-Vektor (1, v, e, f, 1) eines dreidimensionalen Polytops ergibt sich −1+v−e+f−1=0 und damit v−e+f=2.

Jede Facette eines dreidimensionalen Polyeders besitzt mindestens drei Kanten, während jede Kante zu genau zwei Flächen gehört. Doppeltes Abzählen liefert deshalb 2e≥3f. Zusammen mit der Euler-Gleichung folgen e≤3v−6 und f≤2v−4. Durch Dualität erhält man außerdem e≤3f−6 und v≤2f−4. Nach dem Satz von Steinitz ist jeder dreidimensionale ganzzahlige Vektor, der diese Ungleichungen erfüllt, der f-Vektor eines konvexen Polyeders.

In höheren Dimensionen sind zusätzlich die Dehn-Sommerville-Gleichungen wichtig. Für ein simpliziales d-dimensionales Polytop lauten sie h_k=h_{d−k} für alle k. Für k=0 entsprechen sie der Euler-Charakteristik. Bei d>3 liefern die Fälle k≠0 weitere, von ihr linear unabhängige Gleichungen und schränken dadurch den h-Vektor und den f-Vektor stärker ein.

Das von McMullen 1970 erstmals bewiesene Upper-Bound-Theorem gibt eine obere Grenze für die Zahl der Seitenflächen an. Für ein d-dimensionales Polytop mit n Ecken gilt

f_{k−1}≤Σ_{i=0}^{d/2}* (C(d−i,k−i)+C(i,k−d+i)) C(n−d−1+i,i),

wobei C(a,b) Binomialkoeffizienten bezeichnet und bei geradem d der letzte Summand der Summe halbiert wird. Daraus folgt asymptotisch, dass es über alle Dimensionen hinweg höchstens O(n^{⌊d/2⌋}) Seitenflächen gibt.

Schon in vier Dimensionen bilden die möglichen f-Vektoren konvexer Polytope keine konvexe Teilmenge des vierdimensionalen ganzzahligen Gitters. Viele Fragen zu den möglichen Werten solcher Vektoren sind weiterhin ungeklärt.

Berechnung und ganzzahlige Optimierung

Ein algorithmisches Problem besteht darin, für ein gegebenes Polytop und eine natürliche Zahl k zu entscheiden, ob seine Eckenzahl durch k beschränkt ist. Dieses Entscheidungsproblem ist PP-vollständig.

Für Schnittebenenverfahren der ganzzahligen Optimierung ist die Beschreibung der Facetten von Polytopen mit ganzzahligen Ecken besonders wichtig. Viele kombinatorische Optimierungsprobleme lassen sich durch binäre Vektoren darstellen; die zugehörigen 0-1-Polytope besitzen Ecken, die eine Teilmenge der Ecken eines Hyperwürfels bilden. Viele dieser Polytope haben exponentiell oder sogar superexponentiell viele Facetten, weshalb häufig nur eine teilweise Facettenbeschreibung bekannt ist. Ein Beispiel mit einer vollständig bekannten Beschreibung aller Facetten ist das Birkhoff-Polytop.