Direkt zum Inhalt
Vier verliert

Mathematisches Färbeproblem nähert sich der Lösung

Seit Jahrzehnten rätseln Fachleute über die Farbzahl der Ebene. Ein Laie grenzt die Lösung nun mit Computerhilfe ein.
Ein näherungsweise zweidimensionaler Graph in drei Dimensionen vor blauem Hintergrund.

Einen bedeutenden Fortschritt an einem 70 Jahre alten Problem hat nach Ansicht einer Reihe von Fachkollegen der Informatiker und Alterungsforscher Aubrey de Grey erreicht. Wie er in einer Veröffentlichung auf »ArXiv« berichtet, braucht man mindestens fünf Farben, um die Knoten eines beliebigen Graphen so einzufärben, dass jeweils zwei Punkte mit einem vorgegebenen Abstand unterschiedliche Farben besitzen. Bisher galten als mögliche Werte dieser Farbzahl der Ebene die Zahlen Vier bis Sieben. Am Computer konstruierte de Grey nun ein Knotennetz, das sich nur mit mindestens fünf Farben gemäß der Regel einfärben lässt. Derzeit prüfen Fachleute zwar noch, ob es doch eine Möglichkeit mit vier Farben gibt; einige, wie zum Beispiel Gil Kalai von der Hebräischen Universität Jerusalem, haben aber schon erklärt, dass sie den Beweis anerkennen.

Die von de Grey untersuchte Frage nach der Farbzahl der Ebene, das Hadwiger-Nelson-Problem, ähnelt dem Vier-Farben-Problem der Graphentheorie. Dort jedoch dürfen sich die Kanten des Graphen nicht schneiden, während die Länge der Kanten egal ist. Beim Hadwiger-Nelson-Problem ist es praktisch umgekehrt: Man betrachtet nur Punkte mit einer genau vorgegebenen Entfernung voneinander, und es spielt keine Rolle, ob sich die Verbindungslinien schneiden. Wie beim Vier-Farben-Satz spielt der Computer auch bei diesem Färbeproblem eine wesentliche Rolle, denn nur mit technischer Hilfe behält man den Überblick über die unzähligen möglichen Graphen.

Der von de Grey konstruierte Fünf-Farben-Graph mit seinen 1581 Knoten wäre aber auch durch einen Computer nicht in annehmbarer Zeit zu überprüfen gewesen. Allerdings hatte der Hobbymathematiker ihn mit einem Verfahren konstruiert, das gleichzeitig eine Hintertür zu seiner Überprüfung offen ließ. Der neue Graph besteht aus systematisch miteinander verbundenen Moser-Spindeln – jenem fast 70 Jahre alten Graphen aus sieben Punkten, der beweist, dass die Farbzahl der Ebene mindestens vier sein muss. Entlang dieses regelhaften Aufbaus gelang nun der Beweis, dass beim neuen Graphen vier eben nicht gewinnt. Ob die Farbzahl der Ebene nun jedoch fünf, sechs oder sieben ist, bleibt offen. Ebenso, ob wir auf die Antwort darauf noch einmal sieben Jahrzehnte warten müssen.

18/2018

Dieser Artikel ist enthalten in Spektrum - Die Woche, 18/2018

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Vielen Dank!

Partnervideos