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

Résumé Technique : Une Preuve de la Conjecture de Compatibilité de Sabidussi

Énoncé du Problème
L'article traite de la conjecture de compatibilité de Sabidussi dans le contexte des multigraphes connexes finis. Plus précisément, il considère un multigraphe eulérien $G$ (où chaque sommet est de degré pair) avec un degré minimal $\delta(G) \geq 4$. Étant donné un parcours fermé $T$ qui traverse chaque arête exactement une fois (un tour d'Euler), le problème consiste à savoir si les arêtes de $G$ peuvent être partitionnées en circuits (sous-graphes connexes 2-réguliers) de telle sorte qu'aucun circuit ne contienne deux arêtes apparaissant consécutivement dans $T$.

Dans le langage des systèmes de transitions, un tour d'Euler induit un appariement de demi-arêtes à chaque sommet. Une décomposition en circuits est dite « compatible » si aucun circuit n'apparie des demi-arêtes qui sont prescrites comme une transition par le tour. La conjecture affirme qu'une telle décomposition compatible existe toujours sous les contraintes de degré données.

Méthodologie
La preuve procède par une réduction du problème de la théorie des graphes vers un problème combinatoire de mots cycliques, suivie d'une construction algébrique utilisant des arguments de parité sur le corps $\mathbb{F}_2$.

1. Réduction aux Mots Cycliques :
   Les auteurs définissent un mot cyclique $w = (v_0, v_1, \dots, v_{m-1})$ représentant la séquence de sommets visités par le tour d'Euler $T$. Les arêtes du tour correspondent à des « écarts » entre ces lettres. Le problème est reformulé comme la recherche d'une coloration de ces écarts avec des éléments de $\mathbb{F}_2^2$ (une 4-coloration) telle que :

• Les écarts adjacents (correspondant à des arêtes consécutives dans le tour) reçoivent des couleurs différentes.
• Pour chaque sommet $v$ du graphe, les couleurs assignées aux écarts incidents aux occurrences de $v$ satisfont une condition de parité : chaque couleur apparaît un nombre pair de fois parmi les incidences d'écarts.

2. Cadre Algébrique :
   Le cœur de la preuve repose sur deux lemmes établis dans la Section 3 :

• Lemme 3.1 (Parité de la 4-coloration) : Une famille d'éléments de $\mathbb{F}_2^2$ contient chaque élément un nombre pair de fois si et seulement si leur somme linéaire est nulle et leur somme quadratique (définie via une forme bilinéaire spécifique $q(x) = x_1x_2$) est nulle.
• Lemme 3.2 (Équilibrage à trois états) : Un principe de sélection globale stipulant que pour un ensemble fini $U$ et un ensemble à trois éléments $\Sigma$, si certaines conditions de symétrie et de somme nulle sont remplies par une fonction $\beta$, le nombre d'assignations satisfaisant un système de contraintes locales est impair (et donc non nul).

3. Construction de la Coloration :
   La preuve construit la coloration d'écarts requise en :

• Définissant des « motifs locaux » $\Delta_{a,t}$ pour chaque lettre $a$ du mot cyclique, qui assignent des valeurs non nulles dans $\mathbb{F}_2^2$ aux occurrences de $a$ de telle sorte que leur somme soit nulle.
• Définissant des termes d'interaction $\beta_{ab}$ entre les lettres distinctes basés sur l'ordre de leurs occurrences dans le mot.
• Appliquant le Lemme 3.2 pour sélectionner un état spécifique $t_a \in \Omega$ (où $\Omega = \mathbb{F}_2^2 \setminus \{0\}$) pour chaque lettre $a$. Cette sélection garantit que les contraintes d'interaction s'annulent.
• Utilisant ces sélections pour définir une séquence $y_i$ (différences entre les couleurs d'écarts) et les intégrant pour récupérer les couleurs d'écarts $x_i$.
• Vérifiant que la coloration résultante satisfait la condition de degré pair pour chaque classe de couleur à chaque sommet en montrant que la somme des couleurs et la somme de leurs formes quadratiques s'annulent, en invoquant le Lemme 3.1.

Contributions Clés et Résultats

• Théorème 1.1 : L'article prouve que pour tout multigraphe eulérien fini de degré minimal au moins 4 et pour tout tour d'Euler $T$, il existe une coloration $\chi: E(G) \to \mathbb{F}_2^2$ telle que les arêtes consécutives dans $T$ ont des couleurs différentes, et chaque sommet a un degré pair dans chaque classe de couleur.
• Corollaire 1.2 : En conséquence, le graphe $G$ admet une décomposition en circuits compatible avec le système de transition induit par $T$.
• Amélioration de la Double Couverture de Cycles : L'article note que, en présence d'un circuit dominant, le résultat implique qu'un graphe cubique $H$ possède une double couverture de 5 cycles contenant ce circuit. Cela améliore le théorème de la double couverture de 8 cycles récemment prouvé (attribué à OpenAI dans le texte) pour les graphes possédant un circuit dominant.
• Formalisation : La preuve a été entièrement formalisée dans le prouveur de théorèmes Lean.

Signification et Revendications
L'article affirme fournir une preuve complète de la conjecture de compatibilité de Sabidussi, un problème qui était étudié depuis les travaux de Kotzig (1968) et Fleischner (1980). Bien que des résultats précédents aient établi la conjecture pour les graphes planaires, les graphes sans mineur $K_5$, ou pour des contraintes de degré spécifiques, cette preuve traite directement chaque degré pair sans restreindre la classe de graphes au-delà de l'exigence du degré minimal.

Les auteurs déclarent explicitement que la preuve est un renforcement de la conjecture originale, fournissant une 4-coloration avec des propriétés structurelles spécifiques plutôt qu'une simple décomposition. Le travail est présenté comme une résolution définitive de la conjecture, reposant sur une combinaison novatrice de combinatoire de mots cycliques et de lemmes de parité sur des corps finis.

Note sur la Paternité
L'article stipule explicitement que la preuve est entièrement due à « GPT 5.6 Pro », et que la rédaction a été préparée avec l'assistance de « GPT 5.6 Sol ». L'auteur humain, Nikolay Ulyanov, reconnaît le rôle de l'IA dans la génération de l'argument mathématique et de l'exposition.