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 gleichem Abstand unterschiedliche Farben besitzen. Das Problem konnte bisher nicht eindeutig gelöst werden, gehört also zu einem der offenen Probleme der Mathematik, jedoch lässt sich die Lösung auf die Werte 4, 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] ist das Problem (unter Annahme des Auswahlaxioms) äquivalent zur Bestimmung der größten chromatischen Zahl in einem endlichen Einheitsdistanz-Graphen.

Nach Jenson und Toft (1995) zufolge wurde das Problem bereits 1950 von Nelson formuliert und von 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.

Obere und untere Schranken

Sieben-Färbung der Ebene und vierfärbbarer Einheitsdistanz-Graph, Extrembeispiele für die obere und untere Schranke des Hadwiger–Nelson-Problems.

Dass die chromatische Zahl der Ebene mindestens vier sein muss, folgt aus der Existenz eines vierfärbbaren Einheitsdistanz-Graphen mit sieben Knoten, der sogenannten Moser-Spindel, benannt nach den beiden Brüdern William 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₄) 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.

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.

Problemvariationen

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.^[3]

Vorstellbar sind auch Färbungen, bei denen man weitere Bedingungen an die Punktmengen jeder Farbklasse knüpft.^[4] 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 Farbklassen Lebesgue-messbar sein, werden mindestens fünf Farben benötigt. Stellen alle Zusammenhangskomponenten pro Farbklasse konvexe Polygone dar, sind mindestens sechs Farben notwendig.^[5]

Siehe auch

• Vier-Farben-Satz

Literatur

• 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).
• 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 (online).
• Alexander Soifer: The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. Springer, New York 2008, ISBN 978-0387746401.

Weblinks

• Joseph O'Rourke: Problem 57: Chromatic Number of the Plane. The Open Problems Project. Abgerufen am 14. Oktober 2011.
• Bojan Mohar (2001): The chromatic number of the Unit Distance Graph. Abgerufen am 14. Oktober 2011.
• Radoš Radoičić; Géza Tóth: Note on the chromatic number of the space. Abgerufen am 14. Oktober 2011.

Einzelnachweise

1. ↑ Shelah und Soifer, 2003.
2. ↑ De Bruijn und Erdős, 1951.
3. ↑ Coulson, 2002; Radoičić und Tóth.
4. ↑ Croft, Falconer und Guy, 1991.
5. ↑ Coulson, 2004.