Planar-Toroidal Decomposition of $K_{12}$

Cet article démontre, à l'aide d'arguments théoriques et d'une recherche informatique, qu'il est impossible de décomposer le graphe complet $K_{12}$ en un sous-graphe planaire et un sous-graphe toroïdal, tout en identifiant les 123 paires uniques $(G,H)$ qui maximisent le nombre d'arêtes du graphe toroïdal $H$ dans le complémentaire d'un graphe planaire $G$ d'ordre 12.

L'essentiel

🧩 Le Grand Puzzle : Peut-on couper un gâteau en deux morceaux spéciaux ?

Imaginez que vous avez un gâteau très spécial appelé $K_{12}$. Ce n'est pas un gâteau ordinaire : c'est un gâteau où chaque point (ou "morceau") est relié à tous les autres points par une ligne. Avec 12 points, il y a énormément de liens, comme une toile d'araignée géante et parfaite.

Les mathématiciens se posent une question simple mais difficile depuis 1978 : Peut-on couper toutes les lignes de ce gâteau en deux tas distincts ?

1. Le premier tas doit pouvoir être dessiné sur une feuille de papier (un plan) sans que les lignes ne se croisent. C'est ce qu'on appelle un graphe planaire. Imaginez un dessin d'enfant propre sur du papier plat.
2. Le deuxième tas doit pouvoir être dessiné sur un tore (une surface en forme de donut ou de tube) sans que les lignes ne se croisent. C'est ce qu'on appelle un graphe tore. Sur un donut, on peut faire passer des lignes "à travers le trou" pour éviter les croisements, ce qui est impossible sur une feuille plate.

L'objectif de l'article est de répondre à cette question : Est-il possible de faire ce découpage parfait pour un gâteau de 12 points ?

🕵️‍♂️ La Chasse aux Indices (La Théorie)

Avant de lancer les ordinateurs, les auteurs (Allan Bickle et Russell Campbell) ont utilisé leur cerveau pour éliminer des possibilités, un peu comme un détective qui élimine des suspects.

• L'indice des degrés : Ils ont regardé combien de lignes partent de chaque point. Ils ont découvert que si une telle découpe existait, les points devaient avoir un nombre de lignes très précis (ni trop, ni trop peu).
• L'indice des triangles : Sur un papier plat, les lignes forment des triangles. Sur un donut, c'est un peu différent. Ils ont calculé le nombre de triangles nécessaires. Si le nombre de triangles ne correspondait pas à la recette, ils jetaient l'idée.
• Le piège des séparations : Ils ont imaginé couper le gâteau en deux parties. Si la coupe créait une structure trop complexe (comme un pont entre deux îles trop chargé), cela prouvait que la découpe était impossible.

Malgré ces indices, ils n'ont pas pu prouver que c'était impossible seulement avec la théorie. Il restait trop de cas possibles. C'est là que la technologie entre en jeu.

💻 Le Marathon des Ordinateurs

Puisque la théorie ne suffisait pas, les auteurs ont demandé à un ordinateur de faire le travail de force brute. C'est comme si on avait demandé à un robot de tester toutes les façons possibles de dessiner un gâteau sur une feuille, pour voir si le reste pouvait tenir sur un donut.

1. Le stock de gâteaux : Il existe environ 7 595 façons différentes de dessiner un gâteau de 12 points sur une feuille sans croisement. C'est beaucoup !
2. Le test rapide : D'abord, l'ordinateur a éliminé les gâteaux qui avaient des points avec trop de liens (plus de 8). Il en restait encore des milliers.
3. Le test de précision : Ensuite, l'ordinateur a pris chaque gâteau restant, a pris son "complément" (les lignes manquantes pour faire le donut), et a essayé de le dessiner sur un donut.
   • Résultat : Aucun gâteau n'a fonctionné. Même en enlevant une seule ligne du tas du donut, ça ne marchait pas.
   • Résultat : Même en enlevant deux lignes, ça ne marchait toujours pas pour un découpage parfait.

🏆 La Conclusion : La Réponse est "Non"

Après des mois de calculs (environ 60 jours de temps de calcul cumulés), la réponse est claire : Non, il est impossible de découper le gâteau $K_{12}$ en un morceau plat et un morceau en forme de donut.

Cela a deux conséquences importantes :

1. Une conjecture brisée : Une hypothèse mathématique (une supposition) pensait que c'était possible. Les auteurs ont prouvé que cette supposition était fausse pour ce cas précis.
2. Une liste de "presque-gagnants" : Bien qu'aucun découpage parfait n'existe, l'ordinateur a trouvé 123 cas spéciaux où l'on peut presque le faire. Si on enlève deux lignes supplémentaires du tas "donut", alors ça marche ! Ces 123 cas sont comme des "presque-solutions" que les mathématiciens peuvent étudier pour comprendre les limites de la géométrie.

🎨 En Résumé

Imaginez que vous essayez de remplir deux boîtes : une boîte plate (le papier) et une boîte ronde (le donut) avec des fils rouges et bleus. Vous avez un tas de fils très complexe.
Les auteurs ont dit : "Essayons de mettre tous les fils rouges dans la boîte plate et tous les bleus dans la boîte ronde."
Après avoir testé toutes les combinaisons possibles avec un super-ordinateur, ils ont conclu : "C'est impossible pour 12 points."

C'est une victoire pour la logique : parfois, savoir ce qui n'est pas possible est aussi important que de trouver ce qui l'est. Et grâce à eux, nous savons maintenant que pour 12 points, le monde du papier et le monde du donut ne peuvent pas se partager ce gâteau spécifique sans laisser quelques fils de côté.

Résumé technique

Voici un résumé technique détaillé de l'article « Planar-Toroidal Decomposition of K12 » (Décomposition planaire-toroidale de K12) par Allan Bickle et Russell Campbell.

1. Problématique

L'article aborde une question fondamentale en théorie des graphes et en topologie, posée initialement par Anderson et White en 1978 : Le graphe complet $K_{12}$ peut-il être décomposé en deux sous-graphes, l'un étant planaire et l'autre toroïdal ?

Ce problème est lié à la détermination de la constante $N(\gamma, \gamma')$, définie comme la taille du plus petit graphe complet qui ne peut pas être partitionné en deux parties, l'une pouvant être plongée sur une surface de genre $\gamma$ (ici, la sphère, $\gamma=0$) et l'autre sur une surface de genre $\gamma'$ (ici, le tore, $\gamma'=1$).

• Le contexte théorique inclut l'épaisseur toroïdale $\theta_1(K_{12}) = 2$, ce qui signifie que $K_{12}$ peut être décomposé en deux graphes toroïdaux, mais la question spécifique de la décomposition mixte (un planaire + un toroïdal) restait ouverte.
• Une réponse affirmative aurait invalidé une conjecture de Bickle et White (2013) concernant la borne inférieure de la somme des genres d'un graphe et de son complément pour $n=12$.

2. Méthodologie

Les auteurs ont employé une approche hybride combinant des arguments théoriques rigoureux et une recherche informatique exhaustive.

A. Approches Théoriques

Trois méthodes principales ont été utilisées pour éliminer des cas potentiels avant la recherche informatique :

1. Analyse des degrés des sommets :
   • Pour une décomposition $(G, \bar{G})$ de $K_{12}$ où $G$ est planaire maximal et $\bar{G}$ toroïdal, les auteurs ont établi des contraintes strictes sur les degrés.
   • Ils ont démontré que si un sommet a un degré 8 dans $G$, ses voisins non adjacents dans $G$ doivent former un ensemble indépendant.
   • Des inégalités sur les degrés minimums ($\delta$) et maximums ($\Delta$) ont été déduites : $3 \le \delta(G) \le 5$et$5 \le \Delta(G) \le 8$.
2. Comptage des triangles :
   • En utilisant la formule de Goodman, les auteurs ont lié le nombre total de triangles dans $G$ et $\bar{G}$ à la séquence de degrés.
   • Un graphe planaire maximal d'ordre 12 possède 20 triangles, tandis qu'un graphe toroïdal maximal en possède 24. La somme des triangles dans les deux graphes doit satisfaire une équation précise basée sur les degrés. Cela a permis d'éliminer plusieurs séquences de degrés impossibles.
3. Ensembles séparateurs :
   • L'analyse des triangles séparateurs et des cycles séparateurs (4-cycles) a permis de montrer que certaines configurations créeraient des sous-graphes (comme $K_{4,5}$ ou $K_{3,6}$) dont le genre est trop élevé pour être contenu dans un tore ou une sphère, éliminant ainsi de nombreux candidats.

B. Recherche Informatique

Malgré les filtres théoriques, une preuve complète nécessitait l'examen exhaustif des graphes restants.

• Données d'entrée : L'étude a porté sur les 7 595 triangulations planaires maximales d'ordre 12 (issues du Combinatorial Object Server).
• Filtrage initial : 3 476 graphes ont été éliminés car leur degré maximum dépassait 8. D'autres ont été filtrés selon la présence d'ensembles indépendants spécifiques.
• Algorithme de recherche :
  • Les auteurs ont testé le complément de chaque triangulation planaire restante.
  • Ils ont vérifié si le complément pouvait être plongé sur un tore.
  • Ils ont également testé la suppression d'une ou deux arêtes du complément pour voir si un plongement toroïdal devenait possible.
• Outils : La recherche a utilisé des algorithmes de plongement sur tore (complexes, car il n'existe pas d'algorithme linéaire sans erreur pour le tore) et des codes personnalisés en C/C++. La recherche a été exécutée sur plusieurs mois (environ 59 jours pour le cas de la suppression de deux arêtes).

3. Résultats Principaux

1. Non-existence de la décomposition :
   Le résultat central de l'article est la preuve que $K_{12}$ ne peut pas être décomposé en un graphe planaire et un graphe toroïdal. Aucun des 7 595 graphes planaires maximaux d'ordre 12 n'a un complément qui est un graphe toroïdal.

2. Borne sur les arêtes :
   Les auteurs ont démontré que si $G$ est un graphe planaire d'ordre 12 et $H \subseteq G$ est un sous-graphe toroïdal, alors $H$ doit avoir au moins deux arêtes de moins que le graphe planaire maximal correspondant. Autrement dit, un complément planaire maximal ne peut pas être rendu toroïdal par la suppression d'une seule arête.

3. Classification des cas limites :
   Une recherche exhaustive a identifié 123 paires uniques $(G, H)$ où $G$ est une triangulation planaire d'ordre 12 et $H$ est son complément avec exactement deux arêtes supprimées, permettant ainsi un plongement sur le tore. Ces 123 configurations sont listées et visualisées dans les annexes numériques de l'article (GitHub).

4. Réfutation de la Conjecture 1.5 :
   En prouvant qu'aucun graphe $G$ d'ordre 12 ne satisfait $\gamma(G) + \gamma(\bar{G}) = 1$ (où $\gamma$ est le genre), les auteurs ont réfuté la conjecture de Bickle/White pour le cas $n=12$. Cela établit que $N(0, 1) = 12$.

4. Signification et Impact

• Résolution d'un problème ouvert : L'article résout définitivement la question posée par Anderson et White en 1978, fermant le chapitre sur la décomposition mixte de $K_{12}$.
• Avancement de la théorie des genres : Les résultats affinent notre compréhension des limites de l'épaisseur des graphes sur des surfaces de genre mixte et fournissent des contre-exemples précis à des conjectures sur la somme des genres.
• Contribution algorithmique : L'article met en lumière la complexité du plongement sur tore et fournit des données structurées (les 123 paires limites) qui peuvent servir de base pour le développement d'algorithmes d'embedding plus efficaces ou pour des preuves théoriques futures.
• Ressource pour la communauté : Les auteurs ont rendu publics les ensembles de données complets (les 7 595 triangulations, les images générées, et les 123 plongements toroïdaux) via un dépôt GitHub, favorisant la reproductibilité et la résilience de la recherche dans ce domaine.

En conclusion, ce travail combine rigueur mathématique et puissance de calcul pour établir une borne fondamentale dans la théorie des décompositions de graphes complets, démontrant l'impossibilité d'une décomposition planaire-toroïdale pour $K_{12}$.