ZUFÄLLIGE NETZWERKE LASSEN SICH AB EINER FESTEN DICHTE NICHT MEHR FÄRBEN
Man nehme einen Graphen — Punkte, die durch Verbindungen verknüpft sind — und einen Kasten mit Farben. Eine zulässige Färbung mit q Farben gibt jedem Punkt eine von q Farben, sodass zwei verbundene Punkte nie dieselbe haben. Mit wenigen Verbindungen ist das leicht. Mit vielen wird es unmöglich.
Nun baue man den Graphen zufällig: n Punkte, jedes Paar unabhängig mit einer kleinen Wahrscheinlichkeit verbunden, sodass ein Punkt im Mittel d Nachbarn hat. Wenn d wächst, geht der Zufallsgraph von „mit q Farben fast sicher färbbar“ zu „fast sicher nicht“ über. Wo genau geschieht der Umschlag? Diese Frage, für jede feste Anzahl von Farben q ab drei, ist Gegenstand einer neuen Arbeit von Gaia Carenini von der University of Cambridge.
Ein Umschlag, der schwanken könnte
In einer Arbeit aus dem Jahr 1999, die im Literaturverzeichnis aufgeführt ist, bewiesen Achlioptas und Friedgut, dass der Übergang scharf ist: Für jede Größe n gibt es einen kritischen mittleren Grad d_q(n), sodass der Graph knapp darunter fast sicher färbbar ist und knapp darüber fast sicher nicht. Das Fenster, in dem der Umschlag geschieht, schrumpft auf nichts zusammen.
Doch das ließ ein Schlupfloch offen. Nichts hinderte den kritischen Wert selbst daran, zu oszillieren, während die Graphen größer wurden — bei Graphen einer bestimmten Größe an einer Stelle zu liegen, bei größeren leicht woanders, und sich nie einzupendeln. Die Achlioptas–Friedgut-Konvergenzvermutung besagt, dass das nicht geschieht: Für jedes q gibt es eine einzige Konstante d_q, unterhalb derer Zufallsgraphen färbbar sind und oberhalb derer nicht.
Was die Physik vorhergesagt hatte
Die statistische Physik hatte ein Bild davon, was dabei vor sich geht. Während Verbindungen hinzukommen, gruppieren sich die gültigen Färbungen in Cluster: Färbungen innerhalb eines Clusters ähneln einander, während sich zwei Cluster an vielen Punkten unterscheiden. Dann, in einem Stadium namens Kondensation, vereint eine Handvoll großer Cluster einen erheblichen Anteil aller Färbungen — und erst später wird die Menge der Färbungen leer. Diese Organisation erklärt, warum Zählargumente in der Nähe der Schwelle Mühe haben.
Für viele Farben hatten frühere Arbeiten die Schwelle bereits auf einen engen Bereich eingegrenzt: Sie liegt zwischen etwa 2q log q − log q − 2 log 2 und 2q log q − log q − 1, eine Lücke der Breite 2 log 2 − 1, wenn q wächst. Doch „eng“ ist nicht „fest“, und für kleine Farbanzahlen wie drei blieb die Frage offen.
Ein Zwillingsproblem, zuerst angegangen
Das Färben hat einen Zwilling: die Erfüllbarkeit, also das Problem, Variablen die Werte wahr oder falsch so zuzuweisen, dass eine Liste zufälliger logischer Bedingungen allesamt erfüllt ist. Auch dort war bekannt, dass eine scharfe Schwelle existiert, ohne Beweis, dass sie sich einpendelt. In einem Bericht aus dem Jahr 2026, der in der Arbeit zitiert wird, kündigte Carenini einen Beweis dafür an, dass sie es tut, für jede Bedingungslänge ab drei, indem gezeigt wurde, dass das Übergangsfenster sehr schmal ist. Die neue Arbeit überträgt dieses Argument auf das Färben.
Paare, die gemeinsam eingefroren sind
Der Beweis verläuft über eine Kette von Reduktionen. Fügt man zufällige Verbindungen eine nach der anderen hinzu, sei H der Moment, in dem der Graph nicht mehr färbbar ist. Wenn H von einem Zufallsgraphen zum anderen nur wenig schwankt — innerhalb eines Fensters von etwa n/(log n)² Verbindungen —, dann muss sich die Schwelle einpendeln. Eine klassische Ungleichung macht daraus eine Frage über den letzten färbbaren Graphen: Wie viele neue zufällige Verbindungen übersteht er im Mittel?
Hier kommt der Schlüsselbegriff ins Spiel: eingefrorene Paare. Zwei Punkte bilden ein eingefrorenes Paar, wenn jede gültige Färbung ihnen dieselbe Farbe gibt. Eine neue Verbindung ist genau dann fatal, wenn sie ein solches Paar verbindet. Einzelne Punkte können nicht auf eine bestimmte Farbe eingefroren sein, da das Vertauschen der Farben immer eine weitere gültige Färbung ergibt; erzwungen wird eine Beziehung zwischen zwei Punkten. Carenini verfolgt, wie diese eingefrorenen Klassen wachsen, während Verbindungen hinzukommen, indem eine Verbindung oder ein ganzer Punkt gelöscht wird und die Wahlmöglichkeiten betrachtet werden, die wieder auftauchen. Die Abschätzungen zeigen, dass der letzte färbbare Graph nicht lange überleben kann, was das Fenster weit genug verengt, um die Vermutung zu beweisen.
Was unbekannt bleibt
Das Theorem besagt, dass die Schwelle d_q für jedes q ≥ 3 existiert. Es sagt nicht, wo sie liegt: Die Arbeit gibt keinen Wert dafür an, nicht einmal für drei Farben. Die Arbeit ist ein Preprint, das Carenini allein verfasst hat, und wurde nicht von Fachleuten begutachtet. Sie endet mit einer kurzen Erklärung, dass keines ihrer mathematischen Argumente von einem großen Sprachmodell erzeugt wurde.
