Planar-Toroidal Decomposition of $K_{12}$

Die Autoren widerlegen die 1978 von Anderson und White gestellte Vermutung, dass der vollständige Graph $K_{12}$ in einen planaren und einen toroidalen Graphen zerlegt werden kann, indem sie zeigen, dass eine solche Zerlegung unmöglich ist und im besten Fall der toroidale Graph mindestens zwei Kanten weniger als das Komplement des planaren Graphen besitzt.

Das Wesentliche

Stellen Sie sich vor, Sie haben einen riesigen, perfekten Kuchen mit 12 Stück (das ist unser Graph $K_{12}$). Jeder Punkt auf dem Kuchen ist mit jedem anderen Punkt durch eine Zuckerglasur verbunden. Das Ziel der Mathematiker Allan Bickle und Russell Campbell war es, diesen Kuchen in genau zwei Hälften zu teilen, aber mit einer sehr speziellen Regel:

1. Die erste Hälfte muss so flach und glatt sein, dass man sie auf einem Tisch ausbreiten kann, ohne dass sich die Glasur-Linien kreuzen. In der Mathematik nennt man das planar (wie eine flache Landkarte).
2. Die zweite Hälfte darf etwas mehr "Knick" haben. Sie darf auf einem Donut (einem Torus) ausgebreitet werden, ohne dass sich Linien kreuzen. Ein Donut hat ein Loch in der Mitte, was mehr Spielraum für Verwicklungen bietet als ein flacher Tisch.

Die große Frage, die seit 1978 offen war, lautete: Ist es möglich, diesen 12-Punkte-Kuchen so in zwei Teile zu schneiden, dass einer perfekt flach ist und der andere perfekt auf einen Donut passt?

Die Reise der Entdecker

Die Autoren haben sich auf eine epische Suche begeben, um diese Frage zu beantworten. Hier ist, was sie herausfunden, einfach erklärt:

1. Die theoretische Sichtung (Das große Sieb)

Bevor sie Computer anwarfen, haben sie mit Logik und Mathematik versucht, unmögliche Fälle auszusortieren.

• Die Regel der Punkte: Sie stellten fest, dass die Punkte auf dem "flachen" Kuchen bestimmte Regeln einhalten müssen. Wenn ein Punkt zu viele Verbindungen hat, passt er nicht mehr auf den flachen Tisch.
• Das Dreiecks-Problem: Flache Kuchen haben eine bestimmte Anzahl von Dreiecken. Wenn die Anordnung der Punkte zu viele oder zu wenige Dreiecke erzeugt, kann der Rest nicht auf den Donut passen.
• Das Ergebnis dieser Phase: Sie konnten viele Kandidaten ausschließen, aber nicht alle. Es gab immer noch ein paar "Verdächtige", die theoretisch möglich schienen.

2. Der Computer-Check (Der digitale Detektiv)

Da die Logik allein nicht reichte, ließen sie einen Computer alle 7.595 möglichen flachen Kuchen-Strukturen durchsuchen. Das ist wie das Durchsuchen jedes einzelnen Puzzleteils, das es für diese Größe gibt.

• Der erste Test: Der Computer prüfte, ob der komplette Rest des Kuchens (alle Linien, die im flachen Teil fehlten) auf einen Donut passt. Ergebnis: Nein. Nicht einmal ein einziger Fall funktionierte.
• Der zweite Test (Fast geschafft): Da es so nah dran war, fragten sie sich: "Was, wenn wir nur eine Linie im Donut-Teil entfernen?" Der Computer suchte 4 Tage lang. Ergebnis: Immer noch nein.
• Der dritte Test (Der Knackpunkt): "Was, wenn wir zwei Linien entfernen?" Hier passierte etwas Interessantes. Der Computer fand 123 einzigartige Fälle, bei denen der Kuchen fast perfekt passte. Wenn man zwei Linien weglässt, kann man den Rest tatsächlich auf einen Donut legen.

Das Fazit: Die Antwort ist "Nein"

Die Mathematiker haben bewiesen, dass es unmöglich ist, den Kuchen von 12 Punkten in genau einen flachen und einen donutförmigen Teil zu teilen.

• Warum ist das wichtig? Es widerlegt eine Vermutung (eine Art mathematische Hypothese), die besagte, dass so etwas möglich sein müsste.
• Die kleine Hoffnung: Es gibt zwar keine perfekte Lösung, aber sie haben gezeigt, wie nah man dran ist. Man braucht nur zwei Linien weniger im Donut-Teil, damit es funktioniert.

Eine einfache Analogie zum Abschluss

Stellen Sie sich vor, Sie versuchen, ein komplexes Netz aus Gummibändern (die Verbindungen) auf zwei verschiedene Spielzeuge zu verteilen:

1. Ein flaches Brett (Planar).
2. Ein Schlauchreifen (Torus).

Die Forscher haben bewiesen: Wenn Sie 12 Punkte haben, können Sie das Netz nicht so aufteilen, dass alles auf dem Brett liegt und der Rest perfekt auf den Reifen passt. Der Reifen würde immer zu viele Gummibänder haben, die sich kreuzen, es sei denn, Sie schneiden zwei davon einfach ab.

Zusammenfassend: Die Antwort auf die Frage "Kann man $K_{12}$ in Planar und Toroidal zerlegen?" ist ein klares Nein. Aber die Reise hat gezeigt, wie nah wir an der Lösung sind und welche 123 fast-perfekten Muster es gibt, wenn man zwei Linien opfert.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papers „Planar-Toroidal Decomposition of K12" von Allan Bickle und Russell Campbell auf Deutsch.

1. Problemstellung

Das Paper adressiert ein langjähriges Problem der Graphentheorie und Topologie, das erstmals 1978 von Anderson und White aufgeworfen wurde. Es geht um die Frage, ob der vollständige Graph mit 12 Knoten ($K_{12}$) in zwei disjunkte Teilgraphen zerlegt werden kann, wobei der eine Teilgraph planar (auf einer Kugeloberfläche ohne Überschneidungen darstellbar) und der andere toroidal (auf einem Torus ohne Überschneidungen darstellbar) ist.

Formal wird dies als Bestimmung der Größe $N(0, 1)$ definiert, wobei $N(\gamma, \gamma')$ die kleinste Anzahl von Knoten in einem vollständigen Graphen $K_n$ ist, der nicht in zwei Teile zerlegt werden kann, die auf einer Fläche mit $\gamma$ bzw. $\gamma'$ Henkeln eingebettet werden können.

• Bekannte Ergebnisse: $N(0,0) = 9$ (zwei planare Graphen), $N(1,1) = 14$ (zwei toroidale Graphen).
• Die offene Frage war: Ist $N(0,1) = 12$? Das würde bedeuten, dass $K_{12}$ nicht in einen planaren und einen toroidalen Graphen zerlegt werden kann.

Dieses Problem ist eng mit einer Vermutung von Bickle und White (2013) verknüpft, die besagt, dass für alle $n \ge 11$ eine untere Schranke für die Summe der Genus-Werte eines Graphen $G$ und seines Komplements $\bar{G}$ erreicht wird. Für $n=12$ würde diese Vermutung implizieren, dass eine solche Zerlegung existiert ($\gamma(G) + \gamma(\bar{G}) = 1$). Das Ziel des Papers ist es, diese Existenz zu widerlegen.

2. Methodik

Die Autoren verfolgen einen hybriden Ansatz, der theoretische Argumente mit einer umfassenden computergestützten Suche kombiniert.

A. Theoretische Ansätze

Bevor die Suche begann, wurden drei theoretische Filter entwickelt, um den Suchraum der maximalen planaren Graphen der Ordnung 12 drastisch zu reduzieren:

1. Vertex-Grade (Knotengrade):
   • Ein maximaler planarer Graph der Ordnung 12 hat maximal 30 Kanten, ein toroidaler maximal 36. Da $K_{12}$ 66 Kanten hat, müssten beide Faktoren ihre maximal mögliche Kantenzahl erreichen.
   • Es wurden Grenzen für die Minimal- ($\delta$) und Maximalgrade ($\Delta$) hergeleitet. Für einen planaren Faktor $G$ gilt $3 \le \delta(G) \le 5 \le \Delta(G) \le 8$.
   • Es wurde gezeigt, dass Knoten mit Grad 8 in $G$ eine unabhängige Menge im Komplement bilden müssen.
2. Zählen von Dreiecken:
   • Basierend auf einer Formel von Goodman und Sauvé wurde die Anzahl der Dreiecke in $G$ und $\bar{G}$ in Abhängigkeit vom Gradverlauf berechnet.
   • Da ein maximaler planarer Graph 20 Dreiecke und ein toroidaler mindestens 24 benötigt, konnten bestimmte Gradfolgen (Sequenzen) sofort ausgeschlossen werden, da sie nicht genug Dreiecke für beide Graphen zuließen.
3. Trennende Mengen (Separating Sets):
   • Es wurden Sätze bewiesen, die das Vorhandensein bestimmter trennender Dreiecke oder 4-Zyklen in $G$ ausschließen. Beispielsweise führt ein trennendes Dreieck, das Restgraphen der Ordnung 3 und 6 hinterlässt, zu einem Widerspruch bezüglich der Einbettbarkeit des Komplements auf dem Torus.

B. Computergestützte Suche

Da die theoretischen Filter nicht alle Fälle ausschließen konnten, wurde eine exhaustive Suche durchgeführt:

• Datensatz: Es gibt 7.595 nicht-isomorphe maximale planare Graphen (Triangulierungen) der Ordnung 12.
• Filterung: Graphen mit einem Maximalgrad $\Delta \ge 9$ wurden verworfen (basierend auf Lemma 2.2). Dies reduzierte die Anzahl auf 4.119 Kandidaten.
• Suchalgorithmen:
  1. Null Kanten entfernen: Überprüfung, ob das Komplement eines planaren Graphen direkt toroidal ist. (Ergebnis: Keine gefunden).
  2. Eine Kante entfernen: Überprüfung aller Möglichkeiten, eine Kante aus dem Komplement zu entfernen, um eine toroidale Einbettung zu ermöglichen. (Ergebnis: Keine gefunden).
  3. Zwei Kanten entfernen: Überprüfung aller Paare von Kanten im Komplement. Dies war der rechenintensivste Teil (ca. 59 Tage Rechenzeit).
• Tools: Die Suche nutzte Algorithmen zur toroidalen Einbettung und nutzte die Software Surftri von Sulanke zur Generierung der Triangulierungen. Die Ergebnisse wurden in einem GitHub-Repository dokumentiert.

3. Wichtige Beiträge und Ergebnisse

1. Widerlegung der Existenz einer Zerlegung:
   Die Autoren beweisen, dass keine Zerlegung von $K_{12}$ in einen planaren und einen toroidalen Graphen existiert. Damit ist $N(0, 1) = 12$.

2. Widerlegung der Bickle/White-Vermutung für $n=12$:
   Da die Existenz einer solchen Zerlegung äquivalent zur Erreichung der unteren Schranke für $\gamma(G) + \gamma(\bar{G})$ bei $n=12$ ist, wird die Vermutung für diesen spezifischen Fall widerlegt. Es gibt keinen Graphen $G$ der Ordnung 12, für den $\gamma(G) + \gamma(\bar{G}) = 1$ gilt.

3. Schärfere Kantenungleichung:
   Es wird gezeigt, dass wenn $G$ ein planarer Graph der Ordnung 12 ist und $H \subseteq G$ ein toroidaler Teilgraph ist, dann muss $H$ mindestens zwei Kanten weniger haben als $G$. Eine perfekte Aufteilung (bei der beide Faktoren ihre maximale Kantenzahl erreichen) ist unmöglich.

4. Identifikation von Extremfällen:
   Obwohl eine perfekte Zerlegung unmöglich ist, fand die Suche 123 eindeutige Paare $(G, H)$, bei denen $G$ planar ist und $H$ (ein Teilgraph des Komplements von $G$) toroidal ist, wobei genau zwei Kanten aus dem Komplement entfernt werden müssen, um die toroidale Einbettung zu ermöglichen. Diese Fälle stellen die „nächstmögliche" Annäherung an die Zerlegung dar.

5. Ressourcen und Reproduzierbarkeit:
   Die Autoren stellen alle relevanten Daten öffentlich zur Verfügung:

   • Eine Liste der gefilterten Graphen.
   • Bilder der 7.595 planaren Triangulierungen (prozedural generiert).
   • Die 123 gefundenen toroidalen Einbettungen mit zwei fehlenden Kanten.
   • Der Quellcode (C/C++) und die Skripte zur Generierung und Suche.

4. Signifikanz

• Theoretische Klärung: Das Paper schließt eine Lücke in der Theorie der Graphenzerlegung und der Einbettung auf Flächen. Es definiert präzise die Grenzen der „bi-embeddability" für planare und toroidale Graphen.
• Methodischer Fortschritt: Die Arbeit demonstriert erfolgreich die Kombination von tiefgehender graphentheoretischer Analyse (zur Reduktion des Suchraums) mit moderner Rechenleistung, um Probleme zu lösen, die für rein theoretische Beweise zu komplex sind.
• Datenbank für die Forschung: Die bereitgestellten Daten (insbesondere die 123 Extremfälle und die Bilder der Triangulierungen) dienen als wertvolle Ressource für zukünftige Forschungen zu $N(\gamma, \gamma')$, toroidalen Einbettungen und verwandten Problemen in der topologischen Graphentheorie.
• Korrektur von Annahmen: Durch die Widerlegung der Vermutung für $n=12$ wird deutlich, dass die untere Schranke für die Summe der Genus-Werte nicht für alle $n$ erreicht wird, was die Komplexität des Problems unterstreicht.

Zusammenfassend liefert dieses Paper einen vollständigen und verifizierten Beweis dafür, dass $K_{12}$ nicht in einen planaren und einen toroidalen Graphen zerlegt werden kann, und liefert gleichzeitig eine detaillierte Analyse der Fälle, die dieser Bedingung am nächsten kommen.