Hadwiger-Nelson-Problem

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 de Bruijn-Erdős[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.

Obere und untere Schranken[Bearbeiten | Quelltext bearbeiten]

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, 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 () 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, welcher 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.

Problemvariationen[Bearbeiten | Quelltext bearbeiten]

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]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • 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.
  • 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.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. ↑ Shelah und Soifer, 2003.
  2. ↑ Ein Graph ist genau dann -färbbar (), wenn jeder endliche induzierte Teilgraph -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]).
  6. ↑ Polymath-Project16
  7. ↑ Coulson, 2002; Radoičić und Tóth.
  8. ↑ Croft, Falconer und Guy, 1991.
  9. ↑ Coulson, 2004.
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Hadwiger-Nelson-Problem&oldid=244364362“