Chromatische Polynome von Graphen

Graphen sollen so gefärbt werden, dass je zwei verbundene Knoten unterschiedliche Farben bekommen. Die Anzahl der Möglichkeiten einen gegebenen Graphen G mit n Farben zu färben, nennt man χ(G,n). Zum Beispiel ist das berühmte Vierfarbenproblem äquivalent dazu, dass sich jeder ebene Graph mit vier Farben färben läßt, also dass χ(G,4)≥1 für jeden ebenen Graphen G gilt.

Für eine beliebige Kante e von G gilt χ(G,n)=χ(G-e,n)-χ(G/e,n). Mit dieser Formel kann man χ(G,n) rekursiv berechnen und man kann per Induktion beweisen, dass χ(G,n) ein Polynom in n ist, sein Grad ist die Anzahl der Knoten von G. Man nennt es das “chromatische Polynom” des Graphen G. Birkhoff hatte es 1912 eingeführt in der Hoffnung, mit Methoden zur Nullstellenbestimmung von Polynomen letztlich auch die Vierfarbenvermutung lösen zu können. (Was sich nicht erfüllte.)

Das chromatische Polynom des oben abgebildeten Petersen-Graphen ist
.

Beim Betrachten dieses Polynoms fallen zwei Dinge auf:
– die Vorzeichen alternieren
– die Folge der Koeffizienten wächst zunächst (bis n³) und fällt dann.
Folgen mit der zweiten Eigenschaft nennt man unimodal.

Berechnet man charakteristische Polynome weiterer Graphen, so wird man feststellen, dass sie alle diese Eigenschaften haben.
Tatsächlich kann man die alternierenden Vorzeichen der Koeffizienten leicht per Induktion aus der Rekursionsformel beweisen. Dagegen war die zweite Eigenschaft, die Unimodalität der chromatischen Polynome aller Graphen, eine seit 1968 offene Vermutung von Read.

Diese Vermutung ist nun vor einigen Jahren von June Huh bewiesen worden, und zwar überraschenderweise mit Hilfe von Erkenntnissen aus der Singularitätentheorie, einem Teilgebiet der algebraischen Geometrie.

Die algebraische Geometrie kommt so ins Spiel: zu einem Graphen mit K Knoten betrachtet man ein Hyperebenenarrangement im R^K: wenn der i-te und j-te Knoten durch eine Kante verbunden sind, soll die Hyperebene zum Arrangement gehören.

Das chromatische Polynom des ursprünglichen Graphen läßt sich aus der Topologie des Hyperebenen-Komplements berechnen. Sei h(x₁,…,x_K) das Polynom, welches man als Produkt der obigen Linearfaktoren erhält. Dann ist das Komplement des Hyperebenenarrangements. Aus einem Satz von Orlik-Solomon folgt, dass

das chromatische Polynom des Graphen G ist. (Dabei bezeichnet b_i die Betti-Zahlen von D(h), also die Dimensionen der i-ten Homologiegruppen.)

Huh beweist dann, dass diese Bettizahlen sich mittels Singularitätentheorie berechnen lassen. Allgemein sei h ein homogenes Polynom, welches ein Produkt aus linearen Faktoren ist (in unserem Fall aus den ), dann kann man b_i(D(h)) mittels Morsetheorie berechnen und als Ergebnis erhält man die i-te Milnor-Zahl μ_i(h) der Singularität, die das Polynom h im Nullpunkt hat. Diese wird rein algebraisch definiert wie folgt. Betrachte die Ideale , dann ist die Dimension von eine (polynomielle) Funktion in u und v und man definiert μ_i(h) als (n-i)!i! mal den Koeffizienten von u^n-ivⁱ in .
Und schließlich beweist er dann, dass (unter gewissen Voraussetzungen, die durch die spezielle Wahl der Polynome h hier erfüllt sind) die Milnor-Zahlen μ_i(h) eine unimodale Folge bilden, woraus sich dann ergibt, dass auch die Koeffizienten des chromatischen Polynoms eine unimodale Folge bilden. (Dieser Beweis benutzt wiederum, dass die Milnorzahlen mit gewissen gemischten Volumina aus der Konvexgeometrie übereinstimmen, deren Unimodalität bekannt ist.)
Zweifellos eine überraschende Anwendung der algebraischen Geometrie in der Graphentheorie.

June Huh (2012). Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs Journal of the American Mathematical Society, 25, 907-927