Polyedrische Kombinatorik

Polyedrische Kombinatorik ist eine Teildisziplin in der Kombinatorik und diskreten Geometrie (Bereiche der Mathematik), die konvexe Polyeder und höher-dreidimensionale konvexe Polytope studiert.

Insbesondere werden für ein Polytop die Anzahl der Seitenflächen und deren Beschreibung betrachtet. Ungleichungen, die die Anzahlen von Ecken, Kanten und Seitenflächen in beliebigen Polytopen oder bestimmten Subklassen von Polytopen in Verhältnis zueinander setzen, sind von zentraler Bedeutung. Eigenschaften, wie der Durchmesser (Mindestanzahl von Schritten, um von einer Ecke jede beliebige andere Ecke zu erreichen) oder Zusammenhang werden studiert. Unter „polyedrischer Kombinatorik“ versteht man auch die exakte Beschreibung von Seitenflächen bestimmter Polytope (vor allem 0-1-Polytope, deren Ecken eine Teilmenge von Hyperwürfeln sind), die bei ganzzahligen Optimierungsproblemen auftreten.

Seitenflächen und Seitenflächen-zählende Vektoren

Ordnungsdiagramm eines konvexen Polytops

Eine Seitenfläche oder Facette eines konvexen Polytopes P ist eine Teilmenge von P, die der Schnitt von P und einem geschlossenen Halbraum H ist, wobei der Rand von H keinen inneren Punkt von P enthält. Die Dimension einer Seitenfläche ist die Dimension seiner Hülle. Die 0-dimensionalen Seitenflächen sind die Ecken, die 1-dimensionalen Seitenflächen (Kanten) verbinden Paare von Ecken. Man beachte, dass nach dieser Definition auch die leere Menge und das ganze Polytop P selbst Seitenflächen von P sind. Hat P die Dimension d, so werden die Seitenflächen der Dimension p-1 Facetten genannt. Die Seitenflächen von P können per Inklusion partiell geordnet werden. In einem entsprechendes Ordnungsdiagramm ist P ganz oben und die leere Menge ganz unten positioniert.

Ein zentrales Objekt in der polyedrischen Kombinatorik ist der f-Vektor (f₀, f₁ …, f_d − 1) eines Polytops, wobei f_i die Anzahl von i-dimensionalen Seitenflächen des Polytops angibt. Ein (3-dimensionaler) Würfel hat acht Ecken, 12 Kanten und 6 Facetten (2-dimensionale Seitenflächen), sodass sein f-Vektor (8, 12, 6) ist. Der f-Vektor des dualen Polytops enthält genau dieselben Zahlen, jedoch in umgekehrter Reihenfolge. Das duale Polytop des Würfels ist das Oktaeder, es hat den f-Vektor (6, 12, 8).

Der erweiterte f-Vektor (f_-1, f₀, f₁, ..., f_d − 1, f_d) zählt die Anzahl der Objekte auf jeder Ebene des Ordnungsdiagramms der Seitenflächen. Man erhält den erweiterten f-Vektor aus dem (einfachen) f-Vektor durch voranstellen und anhängen jeweils einer 1, wobei f₋₁ = 1 die leere Menge als Seitenfläche zählt und f_d = 1 das Polytop P selbst zählt. Der erweiterte f-Vektor des Würfels ist (1, 8, 12, 6, 1) und der erweiterte f-Vektor des Oktaeders ist (1, 6, 12, 8, 1). Auch wenn die Vektoren dieser Beispiele unimodal sind (die Koeffizienten, von links nach rechts gelesen, wachsen zunächst zum Maximum und werden dann wieder kleiner), gibt es höher-dimensionale Polytope für die dies nicht der Fall ist.

Für simpliziale Polytope (Polytope in denen jede Facette ein Simplex ist) ist es häufig vorteilhaft diese Vektoren zu so genannten h-Vektoren zu transformieren. Dazu seien zunächst die Terme des f-Vektors (ohne der letzten 1) Koeffizienten eines Polynoms $f(x)=\sum _{i}f_{i}x^{d-i-1}$. Dann ist der h-Vektor als die Koeffizienten von $h(x)=f(x-1)$ definiert. Für das Oktaeder gilt beispielsweise $f(x)=x^{3}+6x^{2}+12x+8$ und dann $h(x)=f(x-1)=(x-1)^{3}+6(x-1)^{2}+12(x-1)+8=x^{3}+3x^{2}+3x+1$. Der h-Vektor des Oktaeders ist also (1, 3, 3, 1).

Gleichungen und Ungleichungen

Der wichtigste Zusammenhang zwischen den Koeffizienten eines ƒ-Vektors eines Polytopes ist die Euler-Charakteristik Σ(−1)ⁱf_i = 0, wobei die Summe über die Koeffizienten des erweiterten f-Vektors gehen. Beispielsweise gilt im 3-dimensionalen für den allgemeinen erweiterten f-Vektoren (1, v, e, f, 1) die Gleichung -1 + v - e + f - 1 = 0 bzw. v - e + f = 2. Da jede Facette eines 3-dimensionalen Polyheders mindestens drei Kanten hat, folgt durch doppeltes Abzählen, dass $2e\geq 3f$. Jede Fläche enthält mindestens drei Kanten, während jede Kante genau in zwei Flächen enthalten ist. Dies kann man dazu nutzen, $e$ oder $f$ aus der Euler-Charakteristik zu eliminieren. Man erhält damit $e\leq 3v-6$ und $f\leq 2v-4$. Mit Hilfe von Dualität folgt außerdem $e\leq 3f-6$ und $v\leq 2f-4$. Mit Hilfe vom Satz von Steinitz folgt dann, dass jeder 3-dimensionale ganzzahlige Vektor, der diese Ungleichungen erfüllt, der f-Vektor eines konvexen Polyeder ist.

In höheren Dimensionen sind andere Zusammenhänge wie die Dehn-Sommerville-Gleichung wichtig. Diese ist für simpliziale Polytope mit Hilfe von h-Vektoren $h_{k}=h_{d-k}$ für alle $k$. Für $k=0$ ist sie äquivalent zur Euler-Charakteristik, aber für $d>3$ und $k\neq 0$ erhält man von der Euler-Charakteristik linear unabhängige Gleichungen, die den h-Vektor (und damit auch den f-Vektor) weiter eingrenzen.

Eine andere wichtige Ungleichung zu den Anzahlen der Seitenflächen eines Polytops ist das „upper bound theorem“ (wortwörtlich: „obere Grenze Satz“), zuerst bewiesen von McMullen (1970). Für ein d-dimensionales Polytop mit n Ecken gilt:

$f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {d-i}{k-i}}+{\binom {i}{k-d+i}}\right){\binom {n-d-1+i}{i}},$

wobei der Stern dafür steht, dass der letzte Summand halbiert werden muss, wenn d gerade ist. Dies impliziert, dass es asymptotisch höchstens $\scriptstyle O(n^{\lfloor d/2\rfloor })$ Seitenflächen in allen Dimensionen gibt.

Bereits in vier Dimensionen ist die Menge aller möglichen f-Vektoren konvexer Polytope keine konvexe Teilmenge des 4-dimensinoalen ganzzahligen Gitters. Vieles über die möglichen Werte dieser Vektoren ist weiterhin unbekannt.

Computational properties

Die Entscheidung, ob die Anzahl der Ecken eines gegebenen Polytops durch eine natürliche Zahl k beschränkt ist, ist PP-vollständig.

Facetten von 0-1 Polytopen

Im Kontext von Schnittebenenverfahren für ganzzahlige Optimierungsprobleme ist es wichtig, die Facetten eines Polytops zu beschreiben, deren Ecken ganzzahlig sind. Oft können kombinatorische Optimierungsprobleme mit Hilfe von binären Vektoren beschrieben werden. In diesen Fällen handelt es sich um binäre Optimierungsprobleme. Viele 0-1 Polytope haben exponentiell oder superexponentiell viele Facetten und es ist nur eine partielle Beschreibung der Facetten bekannt. Ein Beispiel für ein Polytop mit vollständiger bekannten Beschreibung aller Facetten ist das Birkhoff-Polytop.

Siehe auch

• Polytop