Petersen_graph_3-coloring.svg

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
n^{10}-15 n^9+104 n^8-455 n^7+1353 n^6-2861 n^5+4275n^4-4305 n^3+2706n^2-704n .

Beim Betrachten dieses Polynoms fallen zwei Dinge auf:
– die Vorzeichen alternieren
– die Folge der Koeffizienten wächst zunächst (bis n3) 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 RK: wenn der i-te und j-te Knoten durch eine Kante verbunden sind, soll die Hyperebene x_i-x_j=0 zum Arrangement gehören.

Arrangement_hyperplans

Das chromatische Polynom des ursprünglichen Graphen läßt sich aus der Topologie des Hyperebenen-Komplements berechnen. Sei h(x1,…,xK) das Polynom, welches man als Produkt der obigen Linearfaktoren x_i-x_j erhält. Dann ist D(h):=\left\{\left[x_1:\ldots:x_K\right]\in {\mathbb C}P^{K-1}\colon h(x_1,\ldots,x_K)\not=0\right\} das Komplement des Hyperebenenarrangements. Aus einem Satz von Orlik-Solomon folgt, dass
(n-1)\sum_i (-1)^ib_i(D(h))n^{K-i} =\chi(G,n)
das chromatische Polynom des Graphen G ist. (Dabei bezeichnet bi 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 x_i-x_j ), dann kann man bi(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 m=(x_1, \ldots , x_K), J=(\frac{\partial h}{\partial x_1},\ldots, \frac{\partial h}{\partial x_K}), dann ist die Dimension von {\mathbb C}\left[x_1,\ldots,x_K\right]/m^uJ^v eine (polynomielle) Funktion in u und v und man definiert μi(h) als (n-i)!i! mal den Koeffizienten von un-ivi in {\mathbb C}\left[x_1,\ldots,x_K\right]/m^uJ^v.
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: Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, Journal of the American Mathematical Society 25 (2012), 907-927.

Kommentare (6)

  1. #1 hubert taber
    22. Juli 2018

    ich realisiere in etwa dieses künstlich geschaffene”problem”.
    nur stelle ich die frage welchen bezug zur REALITÄT hat dieses “problem”?.

    ich bin mehr der tatsächliche problemlöser.
    siehe unter:
    http://scienceblogs.de/mathlog/2016/12/07/kontruktivismus/#comment-234456
    mfg. h.t.

  2. #2 Sven
    22. Juli 2018

    hubert taber,

    wenn du tatsächlich der Meinung bist, dass man nur solche Fragen untersuchen sollte, die einen direkten Bezug zur “REALITÄT” haben, dann ist die Mathematik nicht das richtige Fachgebiet für dich. Vielleicht solltest du dir einen anderen Blog suchen, den du mit deinen Kommentaren beglücken kannst.

  3. #3 hubert taber
    22. Juli 2018

    #melaa

  4. #4 Dirk
    23. Juli 2018

    Ich nehme an, G-e soll der Graph sein, der entsteht, wenn man Kante e aus G entfernt. Aber was bezeichnet G/e?

  5. #5 Thilo
    23. Juli 2018

    Den Graphen, der entsteht, wenn in G die Kante e (einschließlich ihrer beiden Knoten) zu einem Knoten „zusammengedrückt“ wird. Man hat dann also eine Kante weniger und auch einen Knoten weniger, weil aus zwei Knoten einer wird.

  6. […] letzten Beitrag hatten wir über Färbungen von Graphen geschrieben und darüber, dass das chromatische Polynom […]