Von wegen Vier gewinnt. Eine Ebene muss mindestens fünffarbig gescheckt sein, damit kein Farbton sich selbst zu nahe kommt, will ein Forscher bewiesen haben. Das würde ein jahrzehntealtes Problem der Graphentheorie neu stellen.

Färbeprobleme aus der Graphentheorie zeigen ein erstaunliches Zusammenwirken von Ästhetik und Mathematik. Wer Fachkundigen über die Schulter blickt, sucht Farben und Figuren zwar vergeblich, allenfalls sind einzelne Codezeilen farbig markiert. Doch, so scheint es, bezirzt der bloße Begriff Farbe Eingeweihte mit seiner Aura wie Zerebralaphrodisiaka. Wie ist es sonst zu verstehen, dass sie beinah entrückt von einem „schönen Problem“ reden – und Laien ahnen, was sie meinen. So der Fall bei der „Farbzahl der Ebene“, einer knapp 70 Jahre alten Frage, deren Lösung nun einen Schritt näher liegt.

Gil Kalai von der Universität Jerusalem schreibt in seinem Blog : „A major progress on an old standing beautiful problem. Aubrey de Grey proved that the chromatic number of the plane is at least 5.“ Worum geht es? Das sogenannte Hadwiger–Nelson-Problem fragt nach der minimal benötigten Anzahl an Farben um eine Ebene derart einzufärben, dass jeweils zwei Punkte mit Abstand 1 unterschiedliche Farben besitzen. Bisherige Forschungen zeigten, dass nur die Zahlen 4, 5, 6 und 7 als „chromatic number of he plane“ (CNP) infrage kommen.

Eliminier’ die Vier

Der Informatiker und Altersforscher Aubrey de Grey schloss nun auch die Vier aus. Er konstruierte am Computer große Knotennetze mit gleich langen Verbindungsstrecken und zeigte, dass sich die Knoten dieser sogenannten Einheitsgraphen mit fünf Farben zulässig belegen lassen, aber eben nicht mit weniger. Seine Ergebnisse veröffentlichte der Forscher im April 2018 auf dem freien Dokumentenserver arxiv.org.

Ob er beim „Eliminier’ die Vier“ alle Spielregeln des mathematischen Beweisens eingehalten hat, wird noch geprüft. Kalai scheint überzeugt und auch andere stimmen dem Autor eigenen Angaben zufolge bereits zu.

 

Upcycling einer Altbekannten

Damit wäre die Zahl CNP durch 5 und 7 beschränkt. „Seit 1950 gab es an keiner der Schranken eine Verbesserung“, leitet der Autor seinen vermeintlichen Durchbuch ein. Der Verweis auf die Geschichte des Problems kommt nicht von ungefähr. In der Tat basiert sein Beweis auf einem speziellen Untergraphen, dessen Name seit 57 Jahren oft im CNP-Zusammenhang fällt: die Moser-Spindel. Wer immer seither die Vier als eine untere Grenze beweisen möchte, kommt kaum an der Moser-Spindel vorbei. De Grey nutzte ihre bekannte Färbbarkeitseigenschaft und unterzog sie einer Art Upcycling. Er baute viele altbekannte Spindeln zu einem Einheitsgraphen mit 1581 Knoten zusammen und berechnete per Algorithmus, dass der so konstruierte Graph nicht mit vier Farben färbbar ist. (Lesen Sie hier für mehr Hintergrund)

cpn2De Greys Konstruktion: Dieser Graph mit 1581 Knoten ist nicht 4-färbbar, Quelle: de Grey/arxiv.org , Lizenz: gemäß den Bedingungen der Quelle

Algorithmische Abzählreime

Es ist leicht, sich der Farbzahl zu nähern. Beispiel „Zwei“: Legen Spielpartner beim Vier gewinnt ihre Chips zu einem „L“, trifft sich immer eine Farbe selbst, ob gerade oder diagonal.* Die Zwei reicht nicht aus, die gesuchte Farbzahl ist mindestens drei. Eine noch überschaubare Konstruktion gegen die Drei ist die bereits erwähnte Moser-Spindel (Abbildung). „Eene, Meene, Meck“ einmal linksherum, einmal rechtsherum macht die Mecks zu Nachbarn, und das gehört sich nicht. Aber damit ist die Drei noch nicht ganz weg. Vielleicht hat man nur falsch an- und fortgesetzt, wie es beim Haus vom Nikolaus oft passiert. Hier stellt sich jedoch heraus, dass auch Abzählstrophen mit anderer Reihenfolge nicht im Sinn der Färberegeln aufgehen.

20180424 farbzahlmoserExtrembeispiele für die obere und untere Schranke des Hadwiger–Nelson-Problems: Sieben-Färbung (bunt) und vierfärbbare Moser-Spindel (schwarz). Quelle: Wikipedia CC0)

Zum Glück sind bei der Moser-Spindel nur wenige Fälle auszuprobieren. Anders in de Greys Graphen: Es gäbe eine epische Performance, alle Varianten in den 1581 Knoten händisch „auszuzählen“. Wenn es ganz dick kommt, hat der Reim eine Strophenzahl von über neunhundert Stellen! Hätte man ab dem Urknall jede Sekunde eine Strophe gereimt, hätte man heute gerade mal eine achtzehnstellige Strophenzahl hingelegt. Die Methode schafft auch kein Computer in kosmischer Zeit.

De Greys Upcycling schaffte Abhilfe. “Der Test erweist sich als weitaus günstiger im Aufwand an Rechenressourcen als die Bestimmung der Farbzahl ähnlich großer Graphen auf übliche Weise“, so de Grey in der Veröffentlichung. „Der Algorithmus wurde in Mathematica 11 auf einem gewöhnlichen MacBook Air eingegeben und endete nach wenigen Minuten“, heißt es weiter.

Auch wenn die Fachwelt de Greys gehobene Untergrenze bestätigt, bleibt das Hadwiger–Nelson-Problem offen. Denn noch hat niemand gezeigt, dass auch die obere Grenze fünf beträgt. Abzuwarten bleibt auch, ob de Grey wirklich als pentachromator of the plane in die Geschichte der Graphentheorie eingehen wird. Das Thema berührt auch Fragen außerhalb der Mathematik, da sich manche in Färbeprobleme übersetzen lassen. Zum Beispiel tüfteln Färbealgorithmen Stundenpläne aus.

 * Mit einer Spielfeld- und Buchstabenanatomie, bei der Zeh, Ferse und Knöchel des „L“ paarweise gleiche Abstände haben, wie es für die „Einheitsgraphen“ gefordert ist

Text: David Vogel

 

Der Beweis von de Grey basiert auf der Konstruktion eines Graphen, der die Farbzahl 5 besitzt. Dieser Graph besteht aus lauter Moser-Spindeln, die zu kleineren Graphen kombiniert werden. Diese werden dann wiederum zu größeren Graphen zusammengesetzt. Legt man diese größeren Graphen dann wieder übereinander und verbindet bestimmte Knoten, erhält man aus 1581 Knoten bestehenden Graphen, auf dem de Greys Artikel basiert. Für das menschliche Auge ist nur noch ein spinnenwebenartiges Gewirr wahrzunehmen. Wollte man diese Konstruktion nur mit einem Bleistift auf Papier vornehmen, würde man ziemlich schnell die Übersicht verlieren. Um nun zu beweisen, dass dieser Graph die Farbzahl 5 hat, braucht es eine Fallunterscheidung. Man muss zeigen, dass jede mögliche Einfärbung mindestens 5 Farben benötigt. Dieses Unterfangen ist angesichts der Größe und Unüberichtlichkeit des Graphen zum Scheitern verurteilt. Es liegt in der conditio humana, dass wir Fehler machen. Dem Computer hingegen fehlt es zwar an Kreativität, aber er kann viel schneller und mit der richtigen Programmierung auch absolut fehlerfrei rechnen. De Grey hat einen Algorithmus entwickelt, der sämtliche Einfärbungen des Graphen effektiv untersuchen kann. Denn selbst ein Computer ist mit dieser Berechnung ziemlich lange beschäftigt.

Das erste Mal wurden Computer zur Unterstützung eines Beweises bei einem ganz nahen Verwandten des Hadwiger-Nelson Problems verwendet. Die Mathematiker Appel und Haken legten 1976 den ersten computergestützen Beweis für den Vier-Farben-Satz vor. Dieser besagt, dass man jede Landkarte mit 4 Farben ausmalen kann, ohne dass zwei benachbarte Länder dieselbe Farbe besitzen. Sie zeigten, dass sich das Problem auf knapp 2000 Fälle reduzieren ließ und rechneten dann alle diese Fälle mit dem Computer nach. Sie verwendeten dazu allerdings eine sehr komplizierte Assembler-Sprache, sodass der Compuer-Code für andere nur sehr schwer nachzuvollziehen war. Es gab Diskussionen um die Gültigkeit dieses Beweises. Bis heute zweifeln manche Mathematikerinnen und Mathematiker die Validität von computergestützen Beweisen an. Diese haben inzwischen aufgrund der Entwicklung und besseren Lesbarkeit von modernen Programmiersprachen eine höhere Akzeptanz.

Text: Anna Maria Hartkopf, Institut für Mathematik, Freie Universität Berlin