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

Technische Samenvatting: Een Bewijs van Sabidussi's Compatibiliteitsconjectuur

Probleemstelling
Het artikel behandelt de compatibiliteitsconjectuur van Sabidussi binnen de context van eindige samenhangende multigrafen. Specifiek wordt een Euleriaanse multigraaf $G$ beschouwd (waarbij elk knooppunt een even graad heeft) met een minimale graad $\delta(G) \geq 4$. Gegeven een gesloten pad $T$ die elke rand precies één keer doorkruist (een Euler-tour), is de vraag of de randen van $G$ kunnen worden gepartitioneerd in circuits (verbonden 2-reguliere subgrafen) zodanig dat geen enkel circuit twee randen bevat die ope Tendend in $T$ voorkomen.

In de taal van transitiesystemen induceert een Euler-tour een koppeling van halve randen bij elk knooppunt. Een circuitdecompositie is "compatibel" als geen enkel circuit halve randen koppelt die door de tour als een transitie zijn voorgeschreven. De conjectuur stelt dat een dergelijke compatibele decompositie altijd bestaat onder de gegeven graadbeperkingen.

Methodologie
Het bewijs verloopt via een reductie van het graaf theoretische probleem naar een combinatorisch probleem met cyclische woorden, gevolgd door een algebraïsche constructie met behulp van pariteitsargumenten over het lichaam $\mathbb{F}_2$.

1. Reductie naar Cyclische Woorden:
   De auteurs definiëren een cyclisch woord $w = (v_0, v_1, \dots, v_{m-1})$ dat de sequentie van knooppunten vertegenwoordigt die door de Euler-tour $T$ worden bezocht. De randen van de tour komen overeen met "openingen" (gaps) tussen deze letters. Het probleem wordt geherformuleerd als het vinden van een kleuring van deze openingen met elementen uit $\mathbb{F}_2^2$ (een 4-kleuring) zodat:

   • Aangrenzende openingen (overeenkomend met opeenvolgende randen in de tour) verschillende kleuren ontvangen.
   • Voor elk knooppunt $v$ in de graaf de kleuren die aan de openingen incident aan instanties van $v$ worden toegewezen, voldoen aan een pariteitsvoorwaarde: elke kleur komt een even aantal keren voor onder de opening-incidenties.

2. Algebraïsch Kader:
   De kern van het bewijs rust op twee lemma's die in Sectie 3 worden vastgesteld:

   • Lemma 3.1 (Vier-kleur pariteit): Een familie van elementen in $\mathbb{F}_2^2$ bevat elk element een even aantal keren dan en slechts dan als hun lineaire som nul is en hun kwadratische som (gedefinieerd via een specifieke bilineaire vorm $q(x) = x_1x_2$) nul is.
   • Lemma 3.2 (Drie-toestanden balansering): Een globaal selectieprincipe dat stelt dat voor een eindige verzameling $U$ en een verzameling $\Sigma$ met drie elementen, indien bepaalde symmetrie- en nul-somvoorwaarden worden vervuld door een functie $\beta$, het aantal toewijzingen dat aan een systeem van lokale beperkingen voldoet, oneven is (en dus niet nul).

3. Constructie van de Kleuring:
   Het bewijs construeert de vereiste opening-kleuring door:

   • Het definiëren van "lokale patronen" $\Delta_{a,t}$ voor elke letter $a$ in het cyclische woord, die niet-nul waarden in $\mathbb{F}_2^2$ toewijzen aan de instanties van $a$ zodanig dat hun som nul is.
   • Het definiëren van interactietermen $\beta_{ab}$ tussen verschillende letters op basis van de volgorde van hun verschijningen in het woord.
   • Het toepassen van Lemma 3.2 om een specifieke toestand $t_a \in \Omega$ (waarbij $\Omega = \mathbb{F}_2^2 \setminus \{0\}$) te selecteren voor elke letter $a$. Deze selectie zorgt ervoor dat de interactiebeperkingen verdwijnen.
   • Het gebruik van deze selecties om een sequentie $y_i$ (verschillen tussen opening-kleuren) te definiëren en deze te integreren om de opening-kleuren $x_i$ terug te winnen.
   • Het verifiëren dat de resulterende kleuring aan de even-graad conditie voldoet voor elke kleurklasse bij elk knooppunt door aan te tonen dat de som van de kleuren en de som van hun kwadratische vormen verdwijnen, waarbij gebruik wordt gemaakt van Lemma 3.1.

Belangrijkste Bijdragen en Resultaten

• Theorem 1.1: Het artikel bewijst dat voor elke eindige Euleriaanse multigraaf met een minimale graad van ten minste 4 en elke Euler-tour $T$, er een kleuring $\chi: E(G) \to \mathbb{F}_2^2$ bestaat zodanig dat opeenvolgende randen in $T$ verschillende kleuren hebben, en elk knooppunt een even graad heeft in elke kleurklasse.
• Corollary 1.2: Als gevolg hiervan laat de graaf $G$ een circuitdecompositie toe die compatibel is met het transitiesysteem geïnduceerd door $T$.
• Verbetering op Cycle Double Covers: Het artikel merkt op dat in aanwezigheid van een dominerend circuit, het resultaat impliceert dat een kubische graaf $H$ een 5-cycle double cover heeft die dat circuit bevat. Dit is een verbetering ten opzichte van de recent bewezen 8-cycle double cover theorem (toegeschreven aan OpenAI in de tekst) voor grafen met een dominerend circuit.
• Formalisering: Het bewijs is volledig geformaliseerd in de Lean theorem prover.

Betekenis en Claims
Het artikel claimt een volledig bewijs te leveren van de compatibiliteitsconjectuur van Sabidussi, een probleem dat sinds het werk van Kotzig (1968) en Fleischner (1980) is bestudeerd. Hoewel eerdere resultaten de conjectuur hadden vastgesteld voor planaire grafen, $K_5$-minor-vrije grafen, of specifieke graadbeperkingen, behandelt dit bewijs elke even graad direct zonder de klasse van de graaf te beperken buiten de minimale graadvereiste.

De auteurs stellen expliciet dat het bewijs een versterking is van de oorspronkelijke conjectuur, waarbij een 4-kleuring met specifieke structurele eigenschappen wordt geboden in plaats van enkel een decompositie. Het werk wordt gepresenteerd als een definitieve oplossing voor de conjectuur, steunend op een nieuwe combinatie van cyclische woordcombinatoriek en pariteitslemma's over eindige lichamen.

Opmerking over Auteurschap
Het artikel vermeldt expliciet dat het bewijs volledig toe te schrijven is aan "GPT 5.6 Pro", en dat de tekst is voorbereid met assistentie van "GPT 5.6 Sol". De menselijke auteur, Nikolay Ulyanov, erkent de rol van AI bij de generatie van het wiskundige argument en de expositie.