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

Sintesi Tecnica: Una Dimostrazione della Congettura di Compatibilità di Sabidussi

Enunciato del Problema
Il saggio affronta la congettura di compatibilità di Sabidussi nel contesto dei multigrafi finiti connessi. Nello specifico, considera un multigrafo euleriano $G$ (dove ogni vertice ha grado pari) con un grado minimo $\delta(G) \geq 4$. Dato un cammino chiuso $T$ che attraversa ogni arco esattamente una volta (un tour euleriano), il problema chiede se gli archi di $G$ possano essere partizionati in circuiti (sottografi 2-regolari connessi) tali che nessun circuito contenga due archi che appaiono consecutivamente in $T$.

Nel linguaggio dei sistemi di transizione, un tour euleriano induce un accoppiamento di semi-archi in ogni vertice. Una decomposizione in circuiti è "compatibile" se nessun circuito accoppia semi-archi che sono prescritti come una transizione dal tour. La congettura asserisce che una tale decomposizione compatibile esiste sempre sotto i dati vincoli di grado.

Metodologia
La dimostrazione procede attraverso una riduzione dal problema grafetico a un problema combinatorio relativo alle parole cicliche, seguita da una costruzione algebrica utilizzando argomenti di parità sul campo $\mathbb{F}_2$.

1. Riduzione alle Parole Cicliche:
   I autori definiscono una parola ciclica $w = (v_0, v_1, \dots, v_{m-1})$ che rappresenta la sequenza di vertici visitati dal tour euleriano $T$. Gli archi del tour corrispondono a "gap" tra queste lettere. Il problema viene riformulato come la ricerca di una colorazione di questi gap con elementi da $\mathbb{F}_2^2$ (una 4-colorazione) tale che:

   • I gap adiacenti (corrispondenti a archi consecutivi nel tour) ricevano colori diversi.
   • Per ogni vertice $v$ nel grafo, i colori assegnati ai gap incidenti alle occorrenze di $v$ soddisfano una condizione di parità: ogni colore appare un numero pari di volte tra le incidenze dei gap.

2. Framework Algebrico:
   Il cuore della dimostrazione si basa su due lemmi stabiliti nella Sezione 3:

   • Lemma 3.1 (Parità della quattro-colorazione): Una famiglia di elementi in $\mathbb{F}_2^2$ contiene ciascun elemento un numero pari di volte se e solo se la loro somma lineare è zero e la loro somma quadratica (definita tramite una specifica forma bilineare $q(x) = x_1x_2$) è zero.
   • Lemma 3.2 (Bilanciamento a tre stati): Un principio di selezione globale stabilendo che per un insieme finito $U$ e un insieme a tre elementi $\Sigma$, se certe condizioni di simmetria e somma nulla sono soddisfatte da una funzione $\beta$, il numero di assegnazioni che soddisfano un sistema di vincoli locali è dispari (e quindi non nullo).

3. Costruzione della Colorazione:
   La dimostrazione costruisce la colorazione dei gap richiesta tramite:

   • La definizione di "pattern locali" $\Delta_{a,t}$ per ogni lettera $a$ nella parola ciclica, che assegnano valori non nulli in $\mathbb{F}_2^2$ alle occorrenze di $a$ tali che la loro somma sia zero.
   • La definizione di termini di interazione $\beta_{ab}$ tra lettere distinte basata sull'ordine delle loro occorrenze nella parola.
   • L'applicazione del Lemma 3.2 per selezionare uno stato specifico $t_a \in \Omega$ (dove $\Omega = \mathbb{F}_2^2 \setminus \{0\}$) per ogni lettera $a$. Questa selezione assicura che i vincoli di interazione svaniscano.
   • L'uso di queste selezioni per definire una sequenza $y_i$ (differenze tra i colori dei gap) e l'integrazione di esse per recuperare i colori dei gap $x_i$.
   • La verifica che la colorazione risultante soddisfi la condizione di grado pari per ogni classe di colore in ogni vertice, mostrando che la somma dei colori e la somma delle loro forme quadratiche svaniscono, invocando il Lemma 3.1.

Contributi Chiave e Risultati

• Teorema 1.1: Il saggio dimostra che per ogni multigrafo euleriano finito con grado minimo almeno 4 e per ogni tour euleriano $T$, esiste una colorazione $\chi: E(G) \to \mathbb{F}_2^2$ tale che archi consecutivi in $T$ abbiano colori diversi, e ogni vertice abbia grado pari in ogni classe di colore.
• Corollario 1.2: Come conseguenza, il grafo $G$ ammette una decomposizione in circuiti compatibile con il sistema di transizione indotto da $T$.
• Miglioramento della Copertura Doppia di Cicli: Il saggio nota che, in presenza di un circuito dominante, il risultato implica che un grafo cubico $H$ possiede una copertura doppia di cicli a 5 contenente quel circuito. Questo migliora il recentemente dimostrato teorema della copertura doppia di cicli a 8 (attribuito a OpenAI nel testo) per grafi con un circuito dominante.
• Formalizzazione: La dimostrazione è stata pienamente formalizzata nel theorem prover Lean.

Significato e Rivendicazioni
Il saggio sostiene di fornire una dimostrazione completa della congettura di compatibilità di Sabidussi, un problema che è stato studiato sin dal lavoro di Kotzig (1968) e Fleischner (1980). Mentre risultati precedenti avevano stabilito la congettura per grafi planari, grafi senza minor di $K_5$, o specifici vincoli di grado, questa dimostrazione tratta ogni grado pari direttamente senza restringere la classe di grafi oltre al requisito del grado minimo.

Gli autori dichiarano esplicitamente che la dimostrazione è un rafforzamento della congettura originale, fornendo una 4-colorazione con proprietà strutturali specifiche piuttosto che una semplice decomposizione. Il lavoro è presentato come una risoluzione definitiva della congettura, basata su una nuova combinazione di combinatoria delle parole cicliche e lemmi di parità su campi finiti.

Nota sull'Autorialità
Il saggio dichiara esplicitamente che la dimostrazione è interamente dovuta a "GPT 5.6 Pro", e che la stesura è stata preparata con l'assistenza di "GPT 5.6 Sol". L'autore umano, Nikolay Ulyanov, riconosce il ruolo dell'IA nella generazione dell'argomento matematico e dell'esposizione.