Graph Puzzles III.1: A Proof of Sabidussi's Compatibility Conjecture

Technische Zusammenfassung: Ein Beweis von Sabidussis Kompatibilitätsthese

Problemstellung
Die Arbeit befasst sich mit der Kompatibilitätsthese von Sabidussi im Kontext endlicher zusammenhängender Multigraphen. Konkret betrachtet sie einen eulerischen Multigraphen $G$ (bei dem jeder Knoten einen geraden Grad aufweist) mit einem minimalen Grad $\delta(G) \geq 4$. Gegeben sei ein geschlossener Pfad $T$, der jede Kante von $G$ genau einmal durchläuft (ein Euler-Tour), stellt die Problemstellung die Frage, ob die Kanten von $G$ in Kreise (zusammenhängende 2-reguläre Subgraphen) partitioniert werden können, sodass kein Kreis zwei Kanten enthält, die in $T$ aufeinanderfolgend erscheinen.

In der Sprache der Übergangssysteme induziert ein Euler-Tour eine Paarung von Halbkanten an jedem Knoten. Eine Kreiszerlegung ist „kompatibel“, wenn kein Kreis Halbkanten paart, die durch den Tour als Übergang vorgeschrieben sind. Die These besagt, dass eine solche kompatible Zerlegung unter den gegebenen Gradbeschränkungen immer existiert.

Methodik
Der Beweis erfolgt durch eine Reduktion des graphentheoretischen Problems auf ein kombinatorisches Problem mit zyklischen Wörtern, gefolgt von einer algebraischen Konstruktion mittels Paritätsargumenten über dem Körper $\mathbb{F}_2$.

1. Reduktion auf zyklische Wörter:
   Die Autoren definieren ein zyklisches Wort $w = (v_0, v_1, \dots, v_{m-1})$, das die Sequenz der vom Euler-Tour $T$ besuchten Knoten darstellt. Die Kanten des Tours entsprechen den „Lücken“ zwischen diesen Buchstaben. Das Problem wird als das Finden einer Färbung dieser Lücken mit Elementen aus $\mathbb{F}_2^2$ (einer 4-Färbung) umformuliert, so dass:

• Benachbarte Lücken (entsprechend aufeinanderfolgender Kanten im Tour) unterschiedliche Farben erhalten.
• Für jeden Knoten $v$ im Graphen die Farben, die den an den Vorkommen von $v$ angrenzenden Lücken zugewiesen sind, eine Paritätsbedingung erfüllen: Jede Farbe erscheint eine gerade Anzahl von Malen unter den Lücken-Inzidenzen.

2. Algebraischer Rahmen:
   Der Kern des Beweises beruht auf zwei Lemmata, die in Abschnitt 3 etabliert werden:

• Lemma 3.1 (Vierfarben-Parität): Eine Familie von Elementen in $\mathbb{F}_2^2$ enthält jedes Element eine gerade Anzahl von Malen genau dann, wenn ihre lineare Summe Null und ihre quadratische Summe (definiert über eine spezifische bilineare Form $q(x) = x_1x_2$) Null ist.
• Lemma 3.2 (Dreizustands-Balancierung): Ein globales Selektionsprinzip, das besagt, dass für eine endliche Menge $U$ und eine Dreiermenge $\Sigma$, falls bestimmte Symmetrie- und Nullsummenbedingungen durch eine Funktion $\beta$ erfüllt sind, die Anzahl der Zuweisungen, die ein System lokaler Beschränkungen erfüllen, ungerade (und somit ungleich Null) ist.

3. Konstruktion der Färbung:
   Der Beweis konstruiert die erforderliche Lückenfärbung durch:

• Definition von „lokalen Mustern“ $\Delta_{a,t}$ für jeden Buchstaben $a$ im zyklischen Wort, die den Vorkommen von $a$ Werte in $\mathbb{F}_2^2 \setminus \{0\}$ zuweisen, sodass ihre Summe Null ist.
• Definition von Interaktionstermen $\beta_{ab}$ zwischen verschiedenen Buchstaben basierend auf der Reihenfolge ihres Auftretens im Wort.
• Anwendung von Lemma 3.2, um einen spezifischen Zustand $t_a \in \Omega$ (wobei $\Omega = \mathbb{F}_2^2 \setminus \{0\}$) für jeden Buchstaben $a$ zu wählen. Diese Auswahl stellt sicher, dass die Interaktionsbeschränkungen verschwinden.
• Verwendung dieser Selektionen, um eine Sequenz $y_i$ (Differenzen zwischen Lückenfarben) zu definieren und diese zu integrieren, um die Lückenfarben $x_i$ zurückzugewinnen.
• Verifizierung, dass die resultierende Färbung die geraden Gradbedingung für jede Farbklasse an jedem Knoten erfüllt, indem gezeigt wird, dass die Summe der Farben und die Summe ihrer quadratischen Formen verschwinden, unter Anwendung von Lemma 3.1.

Wesentliche Beiträge und Ergebnisse

• Theorem 1.1: Die Arbeit beweist, dass für jeden endlichen eulerischen Multigraphen mit minimalem Grad von mindestens 4 und jeden Euler-Tour $T$ eine Färbung $\chi: E(G) \to \mathbb{F}_2^2$ existiert, so dass aufeinanderfolgende Kanten in $T$ unterschiedliche Farben haben und jeder Knoten in jeder Farbklasse einen geraden Grad aufweist.
• Korollar 1.2: Als Konsequenz lässt sich der Graph $G$ in eine mit dem durch $T$ induzierten Übergangssystem kompatible Kreiszerlegung zerlegen.
• Verbesserung der Zyklus-Doppelabdeckung: Die Arbeit stellt fest, dass das Ergebnis in Gegenwart eines dominierenden Zyklus impliziert, dass ein kubischer Graph $H$ eine 5-Zyklus-Doppelabdeckung besitzt, die diesen Zyklus enthält. Dies verbessert die kürzlich bewiesene 8-Zyklus-Doppelabdeckungstheorie (OpenAI zugeschrieben im Text) für Graphen mit einem dominierenden Zyklus.
• Formalisierung: Der Beweis wurde vollständig im Lean-Theorem-Prover formalisiert.

Bedeutung und Ansprüche
Die Arbeit behauptet, einen vollständigen Beweis für Sabidussis Kompatibilitätsthese zu liefern, ein Problem, das seit der Arbeit von Kotzig (1968) und Fleischner (1980) untersucht wurde. Während frühere Ergebnisse die These für plane Graphen, $K_5$-minor-freie Graphen oder spezifische Gradbeschränkungen etabliert hatten, behandelt dieser Beweis jeden geraden Grad direkt, ohne die Graphklasse über die Anforderung des minimalen Grades hinaus einzuschränken.

Die Autoren geben explizit an, dass der Beweis eine Stärkung der ursprünglichen These ist, indem er eine 4-Färbung mit spezifischen strukturellen Eigenschaften liefert, statt lediglich eine Zerlegung. Die Arbeit wird als definitive Lösung der These präsentiert, die auf einer neuartigen Kombination aus zyklischer Wortkombinatorik und Paritätslemmata über endlichen Körpern beruht.

Hinweis zur Autorschaft
Das Papier gibt ausdrücklich an, dass der Beweis vollständig auf „GPT 5.6 Pro“ zurückgeht und die Ausarbeitung mit Unterstützung von „GPT 5.6 Sol“ erstellt wurde. Der menschliche Autor, Nikolay Ulyanov, erkennt die Rolle der KI bei der Generierung des mathematischen Arguments und der Exposition an.