Hadwiger-Nelson-Problem

Das Hadwiger-Nelson-Problem ist ein nach Hugo Hadwiger und Edward Nelson benanntes Problem der geometrischen Graphentheorie. Gesucht wird die minimal benötigte Anzahl an Farben, um eine Ebene derart einzufärben, dass jeweils zwei Punkte mit Abstand 1 unterschiedliche Farben besitzen. Das Problem konnte bisher nicht gelöst werden, gehört also zu den offenen Problemen der Mathematik, jedoch lässt sich die Lösung auf die Werte 5, 6 oder 7 einschränken. Die richtige Lösung hängt vermutlich davon ab, welche Axiome aus der Mengenlehre vorausgesetzt werden.^[1]

Das Problem lässt sich graphentheoretisch wie folgt formulieren: Sei G ein Einheitsdistanz-Graph in der Ebene, also ein unendlicher Graph, bei dem die Knoten mit den Punkten in der Ebene identisch sind. Außerdem sollen die Punkte genau dann durch eine Kante verbunden werden, wenn sie einen euklidischen Abstand von 1 besitzen. Dann besteht das Hadwiger-Nelson-Problem in der Bestimmung der chromatischen Zahl von G. Folglich wird das Problem auch häufig „Bestimmung der chromatischen Zahl in der Ebene“ genannt. Nach dem Satz von Erdős und de Bruijn^[2][3][4] ist das Problem (unter Annahme des Auswahlaxioms) äquivalent zur Bestimmung der größten chromatischen Zahl in einem endlichen Einheitsdistanz-Graphen.

Nach Jensen und Toft (1995) wurde das Problem bereits 1950 von Edward Nelson formuliert und von Martin Gardner 1960 zum ersten Mal veröffentlicht. Hadwiger hat 1945 gezeigt, dass jede Überdeckung der Ebene aus fünf kongruenten abgeschlossenen Mengen eine Kante mit Abstand 1 in einer ihrer Mengen enthält. Hadwiger erwähnte das Problem auch in einer späteren Veröffentlichung (1961). Das Problem und seine Geschichte wurden 2008 ausführlich von Soifer abgehandelt.

Dass die chromatische Zahl der Ebene mindestens vier sein muss, folgt aus der Existenz eines vierfärbbaren, aber nicht dreifärbbaren Einheitsdistanz-Graphen mit sieben Knoten, der sogenannten Moser-Spindel, benannt nach den beiden Brüdern William Oscar Jules Moser und Leo Moser. Dieser Graph besteht aus zwei gleichseitigen Dreiecken, die an einem gemeinsamen Knoten x verbunden sind. An der gegenüberliegenden Seite von x befindet sich jeweils ein weiteres gleichseitiges Dreieck mit den Knotenpunkten y und z, zwischen denen ebenfalls eine Kante verläuft. Die Moser-Spindel kann auch graphentheoretisch mit Hilfe der Hajós-Konstruktion erzeugt werden, bei der man mit zwei vollständigen Graphen mit jeweils vier Knoten ( K 4 {\displaystyle K_{4}} ) startet. Falls die Ebene dreifärbbar wäre, würde die Färbung die Dreiecke veranlassen, dass y und z die gleiche Farbe wie x bekommen. Da y und z jedoch durch eine Kante verbunden sind, ist keine gültige Färbung möglich. Somit sind also mindestens vier Farben nötig, um den Graph und die zugehörige Ebene einzufärben.

Eine Verbesserung dieser unteren Schranke auf 5 wurde erst im Jahr 2018, nach über 60 Jahren, durch den Biologen Aubrey de Grey erreicht. In seinem Paper beschreibt er explizit die Konstruktion eines Einheitsdistanz-Graphen, der nicht mit vier Farben gefärbt werden kann. Dazu verwendete er eine Vielzahl miteinander verknüpfter Moser-Spindeln.^[5] Die Größe des von de Grey angegebenen Graphen beträgt 1581 Knoten. Im Polymath16-Projekt wird von verschiedenen Wissenschaftlern gemeinsam der Versuch unternommen, einen kleineren Einheitsdistanz-Graphen, der 5 Farben benötigt, zu finden. Der derzeit kleinste solche Graph besitzt 510 Knoten und wurde im August 2019 von Jaan Parts konstruiert.^[6]

Die Oberschranke von sieben für die chromatische Zahl folgt aus der Existenz einer Unterteilung der Ebene in regelmäßige Sechsecke, deren Durchmesser etwas weniger als 1 betragen muss. Dann lassen sich sieben Farben in wiederholendem Muster anordnen und man erhält eine Sieben-Färbung der Ebene. Nach Soifer (2008) wurde diese Methode erstmals von John R. Isbell entdeckt.

Das Problem kann leicht auf höhere Dimensionen ausgeweitet werden. In der dritten Dimension gibt es wie in der Ebene keine eindeutige Lösung. Es wurde jedoch gezeigt, dass die chromatische Zahl in diesem Fall zwischen 6 und 15 liegen muss.^[7]

Vorstellbar sind auch Färbungen, bei denen man weitere Bedingungen an die Punktmengen jeder Farbklasse knüpft.^[8] Solche Einschränkungen könnten zu einer Erhöhung der benötigten Farben führen, da bestimmte Färbungen ihre Gültigkeit verlieren würden. Sollen zum Beispiel zusätzlich alle Zusammenhangskomponenten pro Farbklasse konvexe Polygone sein, sind mindestens sechs Farben notwendig.^[9]

• Vier-Farben-Satz

• Nicolaas Govert de Bruijn, Paul Erdős: A colour problem for infinite graphs and a problem in the theory of relations. In: Nederl. Akad. Wetensch. Proc. Ser. A 54. 1951, S. 371–373. 
• K. B. Chilakamarri: The unit-distance graph problem: a brief survey and some new results. In: Bull Inst. Combin. Appl. 8. 1993, S. 39–60. 
• D. Coulson: A 15-colouring of 3-space omitting distance one. In: Discrete Math. 256. 2002, S. 83–90, doi:10.1016/S0012-365X(01)00183-2. 
• D. Coulson: On the chromatic number of plane tilings. In: J. Austral. Math. Soc. 77 (2). 2004, S. 191–196, doi:10.1017/S1446788700013574 (online [abgerufen am 15. August 2024]). 
• Hallard T. Croft, Kenneth J. Falconer, Richard Kenneth Guy: Unsolved Problems in Geometry. Springer-Verlag, 1991 (Problem G10). 
• Martin Gardner: Mathematical Games. In: Scientific American 203/4. 1960, S. 180. 
• Hugo Hadwiger: Überdeckung des euklidischen Raumes durch kongruente Mengen. In: Portugal. Math. 4. 1945, S. 238–242. 
• Hugo Hadwiger: Ungelöste Probleme No. 40. In: Elem. Math. 16. 1961, S. 103–104. 
• Tommy R. Jensen, Bjarne Toft: Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995, S. 150–152. 
• Saharon Shelah, Alexander Soifer: Axiom of choice and chromatic number of the plane. In: Journal of Combinatorial Theory, Series A 103 (2). 2003, S. 387–391, doi:10.1016/S0097-3165(03)00102-X. 
• Alexander Soifer: The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. Springer, New York 2008, ISBN 978-0-387-74640-1. 

• Joseph O’Rourke: Problem 57: Chromatic Number of the Plane. In: The Open Problems Project. Archiviert vom Original am 25. Oktober 2014; abgerufen am 15. August 2024 (englisch). 
• Bojan Mohar: The chromatic number of the Unit Distance Graph. 2001, abgerufen am 15. August 2024 (englisch). 
• Hadwiger-Nelson problem – PolymathWiki. In: Polymath-Project. Archiviert vom Original am 18. August 2022; abgerufen am 15. August 2024 (englisch). 
• Veronika Mischitz, aka Frau Kirschvogel: Jagd auf CNP. In: Helmholtz-Wissenschaftscomic „Klar Soweit?“ No.52. 29. Mai 2018, abgerufen am 15. August 2024. 

1. ↑ Shelah und Soifer, 2003.
2. ↑ Ein Graph ist genau dann k {\displaystyle k} -färbbar ( k ∈ N {\displaystyle k\in \mathbb {N} } ), wenn jeder endliche induzierte Teilgraph k {\displaystyle k} -färbbar ist.
3. ↑ Martin Aigner: Combinatorial Theory. Springer-Verlag, Berlin u. a. 1979, ISBN 3-540-90376-3, S. 410. 
4. ↑ De Bruijn und Erdős, 1951.
5. ↑ Aubrey D.N.J. de Grey: The Chromatic Number of the Plane Is at least 5. In: Geombinatorics. Band 28, 2018, S. 5–18 (arXiv [PDF; abgerufen am 15. August 2024]). 
6. ↑ Polymath-Project16. (Memento vom 24. Oktober 2022 im Internet Archive)
7. ↑ Coulson, 2002; Radoičić und Tóth.
8. ↑ Croft, Falconer und Guy, 1991.
9. ↑ Coulson, 2004.