www.wikidata.de-de.nina.az

Hadwiger Nelson Problem Das ist ein nach Hugo Hadwiger und Edward Nelson benanntes Problem der Geometrischen Graphentheo

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.

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

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

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

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.

Vorstellbar sind auch Färbungen, bei denen man weitere Bedingungen an die Punktmengen jeder Farbklasse knüpft. 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.

Siehe auch Bearbeiten

Literatur 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

Einzelnachweise 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Hadwiger Nelson Problem ist ein nach Hugo Hadwiger und Edward Nelson benanntes Problem der Geometrischen Graphentheorie Gesucht wird die minimal benotigte Anzahl an Farben um eine Ebene derart einzufarben dass jeweils zwei Punkte mit Abstand 1 unterschiedliche Farben besitzen Das Problem konnte bisher nicht gelost werden gehort also zu den offenen Problemen der Mathematik jedoch lasst sich die Losung auf die Werte 5 6 oder 7 einschranken Die richtige Losung hangt vermutlich davon ab welche Axiome aus der Mengenlehre vorausgesetzt werden 1 Das Problem lasst 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 Ausserdem 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 haufig Bestimmung der chromatischen Zahl in der Ebene genannt Nach dem Satz von de Bruijn Erdos 2 3 4 ist das Problem unter Annahme des Auswahlaxioms aquivalent zur Bestimmung der grossten 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 veroffentlicht Hadwiger hat 1945 gezeigt dass jede Uberdeckung der Ebene aus funf kongruenten abgeschlossenen Mengen eine Kante mit Abstand 1 in einer ihrer Mengen enthalt Hadwiger erwahnte das Problem auch in einer spateren Veroffentlichung 1961 Das Problem und seine Geschichte wurden 2008 ausfuhrlich von Soifer abgehandelt Inhaltsverzeichnis 1 Obere und untere Schranken 2 Problemvariationen 3 Siehe auch 4 Literatur 5 Weblinks 6 EinzelnachweiseObere und untere Schranken Bearbeiten nbsp Sieben Farbung der Ebene und vierfarbbarer Einheitsdistanz Graph Extrembeispiele fur die obere und untere Schranke des Hadwiger Nelson ProblemsDass die chromatische Zahl der Ebene mindestens vier sein muss folgt aus der Existenz eines vierfarbbaren aber nicht dreifarbbaren Einheitsdistanz Graphen mit sieben Knoten der sogenannten Moser Spindel benannt nach den beiden Brudern William Oscar Jules Moser und Leo Moser Dieser Graph besteht aus zwei gleichseitigen Dreiecken die an einem gemeinsamen Knoten x verbunden sind An der gegenuberliegenden Seite von x befindet sich jeweils ein weiteres gleichseitiges Dreieck mit den Knotenpunkten y und z zwischen denen ebenfalls eine Kante verlauft Die Moser Spindel kann auch graphentheoretisch mit Hilfe der Hajos Konstruktion erzeugt werden bei der man mit zwei vollstandigen Graphen mit jeweils vier Knoten K 4 displaystyle K 4 nbsp startet Falls die Ebene dreifarbbar ware wurde die Farbung 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 gultige Farbung moglich Somit sind also mindestens vier Farben notig um den Graph und die zugehorige Ebene einzufarben Eine Verbesserung dieser unteren Schranke auf 5 wurde erst im Jahr 2018 nach uber 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 gefarbt werden kann Dazu verwendete er eine Vielzahl miteinander verknupfter Moser Spindeln 5 Die Grosse des von de Grey angegebenen Graphen betragt 1581 Knoten Im Polymath16 Projekt wird von verschiedenen Wissenschaftlern gemeinsam der Versuch unternommen einen kleineren Einheitsdistanz Graphen der 5 Farben benotigt zu finden Der derzeit kleinste solche Graph besitzt 510 Knoten und wurde im August 2019 von Jaan Parts konstruiert 6 Die Oberschranke von sieben fur die chromatische Zahl folgt aus der Existenz einer Unterteilung der Ebene in regelmassige Sechsecke deren Durchmesser etwas weniger als 1 betragen muss Dann lassen sich sieben Farben in wiederholendem Muster anordnen und man erhalt eine Sieben Farbung der Ebene Nach Soifer 2008 wurde diese Methode erstmals von John R Isbell entdeckt Problemvariationen BearbeitenDas Problem kann leicht auf hohere Dimensionen ausgeweitet werden In der dritten Dimension gibt es wie in der Ebene keine eindeutige Losung Es wurde jedoch gezeigt dass die chromatische Zahl in diesem Fall zwischen 6 und 15 liegen muss 7 Vorstellbar sind auch Farbungen bei denen man weitere Bedingungen an die Punktmengen jeder Farbklasse knupft 8 Solche Einschrankungen konnten zu einer Erhohung der benotigten Farben fuhren da bestimmte Farbungen ihre Gultigkeit verlieren wurden Sollen zum Beispiel zusatzlich alle Zusammenhangskomponenten pro Farbklasse konvexe Polygone sein sind mindestens sechs Farben notwendig 9 Siehe auch BearbeitenVier Farben SatzLiteratur BearbeitenNicolaas Govert de Bruijn Paul Erdos 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 Uberdeckung des euklidischen Raumes durch kongruente Mengen In Portugal Math 4 1945 S 238 242 Hugo Hadwiger Ungeloste 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 BearbeitenJoseph O Rourke Problem 57 Chromatic Number of the Plane In The Open Problems Project Abgerufen am 14 Oktober 2011 Bojan Mohar The chromatic number of the Unit Distance Graph 2001 abgerufen am 14 Oktober 2011 Hadwiger Nelson problem PolymathWiki In Polymath Project Abgerufen am 23 April 2018 Veronika Mischitz aka Frau Kirschvogel Jagd auf CNP In Helmholtz Wissenschaftscomic Klar Soweit No 52 Abgerufen am 30 Mai 2018 Einzelnachweise Bearbeiten Shelah und Soifer 2003 Ein Graph ist genau dann k displaystyle k nbsp farbbar k N displaystyle k in mathbb N nbsp wenn jeder endliche induzierte Teilgraph k displaystyle k nbsp farbbar ist Martin Aigner Combinatorial Theory Springer Verlag Berlin u a 1979 ISBN 3 540 90376 3 S 410 De Bruijn und Erdos 1951 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 Polymath Project16 Coulson 2002 Radoicic und Toth Croft Falconer und Guy 1991 Coulson 2004 Abgerufen von https de wikipedia org w index php title Hadwiger Nelson Problem amp oldid 235724062