150px|mini|Der Petersen-Graph ist ein Einheitsdistanz-Graph: er kann so gezeichnet werden, dass jede Kante gleich lang ist.
Ein Einheitsdistanz-Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist. Kanten eines Einheitsdistanz-Graphen dürfen sich überschneiden, d. h., der Graph muss nicht immer planar sein. Ein Einheitsdistanz-Graph ohne Überschneidungen wird Streichholzgraph genannt.
Das Problem von Hadwiger und Nelson beschäftigt sich mit der chromatischen Zahl des Graphen. Jeder Einheitsdistanz-Graph kann mit höchstens sieben Farben eingefärbt werden, bekanntlich existieren aber auch einige Graphen, die mindestens vier Farben benötigen. Ein anderes bekanntes Problem befasst sich mit der Frage, wie hoch das Verhältnis von Kanten- zu Knotenanzahl sein kann. Die genaue asymptotische Größenordnung dieser Kantenanzahl ist weiterhin unbekannt; eine lange verbreitete Vermutung von Erdős, nach der sie höchstens wie wachsen sollte, wurde 2026 widerlegt.
Beispiele mini|150px|Hyperwürfel-Graph Q4 als Einheitsdistanz-Graph. Folgende Graphen sind Einheitsdistanz-Graphen: Jeder zyklische Graph Jeder Gittergraph Jeder Hyperwürfel-Graph Der Petersen-Graph Der Heawood-Graph Das Wagenrad W7
Strikter Einheitsdistanz-Graph 150px|mini|Einheitsdistanz-Variante des Möbius–Kantor-Graphen, bei dem einige nicht benachbarte Knoten ebenfalls eine Einheitsdistanz haben. Einige Definitionen in der Literatur lassen die Möglichkeit zu, dass nicht benachbarte Knotenpaare ebenfalls Einheitsdistanz haben dürfen. Zum Beispiel gibt es eine Variante des Möbius–Kantor-Graphen von dieser Art.
Nach dieser abgeschwächten Definition sind alle verallgemeinerten Petersen-Graphen Einheitsdistanz-Graphen.Žitnik, Horvat und Pisanski, 2010. Um beide Definitionen zu unterscheiden, wird ein Graph, bei dem nur benachbarte Knoten eine Einheitsdistanz haben dürfen, strikter Einheitsdistanz-Graph genannt.Gervacio, Lim und Maehara, 2008.
Entfernt man beim Wagenrad W7 eine Speiche, erhält man einen nicht-strikten Teilgraphen. Es ist nicht möglich, die Knoten und insbesondere die beiden Endpunkte der fehlenden Speiche so anzuordnen, dass man wieder einen strikten Graphen erhält.Soifer, 2008, S. 94.
Zählung von Einheitsdistanzen Paul Erdős stellte 1946 das Problem, wie man in einer Menge von n Punkten die Anzahl an Punktpaaren mit Einheitsdistanz bestimmt. Schreibt man für die maximale Anzahl solcher Punktpaare unter allen ebenen Punktmengen mit n Punkten, fragt das Problem nach dem asymptotischen Wachstum von . Graphentheoretisch formuliert: Wie dicht kann ein Einheitsdistanz-Graph sein?
Der Hyperwürfel-Graph besitzt für die Anzahl an Einheitsdistanzen eine untere Schranke proportional zu . Werden die Punkte in einem Quadratgitter mit vorsichtig gewählten Zwischenräumen angeordnet, gibt es nach Erdős eine verbesserte untere Schranke von
für eine geeignete Konstante . Erdős vermutete lange, dass diese Gitterkonstruktionen im Wesentlichen optimal seien; in einer stärkeren Form der Vermutung sollte es eine absolute Konstante geben, so dass für alle hinreichend großen die obere Schranke gilt. Erdős bot ein Preisgeld von , falls jemand eine ähnliche Funktion für die obere Schranke findet.Kuperberg, 1992.
Im Jahr 2026 wurde diese Vermutung widerlegt: Eine von OpenAI veröffentlichte Konstruktion zeigt, dass es ein festes und unendlich viele positive ganze Zahlen gibt, für die gilt. Eine begleitende Arbeit mehrerer Mathematiker gibt eine gekürzte, menschlich überprüfte und leicht verallgemeinerte Fassung des Beweises. Die Konstruktion lässt sich als hochdimensionale Variante der Arithmetik hinter Erdős’ klassischer Gitterkonstruktion verstehen: An die Stelle der gaußschen ganzen Zahlen treten Zahlkörper über total reellen Körpern wachsenden Grades; vollständig zerlegte Primzahlen, beschränkte Wurzeldiskriminanten und Klassenkörpertürme liefern viele Elemente, die unter allen komplexen Einbettungen Betrag 1 haben und nach einer Gittereinbettung sowie Projektion Einheitsdistanzen in der Ebene erzeugen.
Die beste bekannte obere SchrankeJoel Spencer, Endre Szemerédi und William Trotter, 1984. liegt weiterhin proportional zu
Diese Grenze kann auch als Zählung der Inzidenzen zwischen Punkten und Einheitskreisen betrachtet werden und ist nah mit dem Satz von Szemerédi und Trotter für Inzidenzen zwischen Punkten und Geraden verwandt. Das Einheitsdistanz-Problem von Erdős ist daher weiterhin offen, liegt aber nach der Widerlegung der früheren Vermutung nun zwischen einer bekannten unteren Schranke für unendlich viele und der allgemeinen oberen Schranke .
Verallgemeinerung für höhere Dimensionen Die Definition des Einheitsdistanz-Graphen kann selbstverständlich auch auf höherdimensionale euklidische Räume verallgemeinert werden. Jeder Graph kann als Punktmenge in eine genügend hohe Dimension eingebettet werden. Maehara und Vojtěch Rödl zeigten 1990, dass die notwendige Dimension, um einen Graphen auf diese Weise einzubetten, durch den doppelten Maximalgrad des Graphen beschränkt ist.
Die notwendige Dimension, um einen Graphen so einzubetten, dass alle Kanten Einheitsdistanz haben, und die notwendige Dimension, um einen Graphen so einzubetten, dass alle Kanten genau den Einheitsdistanz-Paaren entsprechen, können sich stark voneinander unterscheiden: Der Johnson-Graph mit kann so in die vierte Dimension eingebettet werden, dass all seine Kanten Einheitsdistanz haben, benötigt jedoch Dimensionen für eine Einbettung, bei der nur die Kanten Einheitsdistanz-Paare sind.Erdős und Simonovits, 1980.
Siehe auch Satz von Beckman und Quarles
Literatur
Weblinks
Einzelnachweise
Kategorie:Geometrischer Graph