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.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.