7 278 601 292 779 396 715. C'est exactement le nombre de graphes cordaux différents (des graphes sans cycles induits de longueur quatre ou plus) que l'on peut construire sur vingt sommets, en considérant les structures sans noms. Ce nombre n'est pas le fruit d'un casse-tête pour supercalculateur, mais le résultat exact d'un nouvel algorithme qui considère la symétrie comme un outil, et non comme un obstacle.

Imaginez un kaléidoscope : quelques fragments de verre coloré engendrent un motif infini en se multipliant dans les miroirs. Dans le problème de l'énumération des graphes non étiquetés (où les sommets sont indistinguables), les symétries sont ces mêmes miroirs : des permutations de sommets qui laissent le graphe inchangé. Pour compter tous les graphes non étiquetés, il faut tenir compte de chaque réflexion possible. C'est ici qu'intervient le lemme de Burnside : la moyenne, sur toutes les permutations, du nombre de graphes invariants sous une permutation donnée est égale au nombre cherché. Le problème, c'est que le nombre de permutations est la factorielle du nombre de sommets, et pour n=20, cela fait 2,43×$10^{18}$ possibilités. Mais l'algorithme contourne cette avalanche en s'appuyant sur l'« évaporation ».

L'évaporation est un processus élégant : d'un graphe cordal, on retire à plusieurs reprises des sommets simpliciaux (dont les voisins forment une clique), jusqu'à obtenir un graphe vide. En 2021, une approche dans l'esprit de John von Neumann — la programmation dynamique — a permis de compter rapidement les graphes cordaux étiquetés. Mais comment la transposer dans le monde des symétries ? La réponse : faire évaporer d'un coup des orbites entières, c'est-à-dire des groupes de sommets qui se transforment les uns dans les autres par permutation. C'est ainsi qu'est née l'évaporation orbitale.

Le moment le plus délicat est lorsque l'orbite est hétérogène et que ses parties sont reliées par des passerelles complexes. C'est alors qu'intervient la décomposition en faisceaux diviseurs. Si une permutation contient un cycle de longueur c et qu'une composante connexe du graphe s'étend sur plusieurs orbites, elle se décompose en d « faisceaux » identiques, chacun étant symétrique par rapport à un groupe plus petit — comme si, dans le kaléidoscope, ce n'était pas tout le fragment qui se reflétait, mais une partie. Cette astuce réduit le calcul à un appel récursif du même problème dans un monde réduit : au lieu du groupe initial, on considère un groupe d'ordre d fois plus petit. La récursion est au cœur du schéma de calcul qui énumère soigneusement les types de cycles et accumule les contributions.

Ainsi, pas à pas, on est arrivé à n=20. L'algorithme non seulement coïncide avec les valeurs connues jusqu'à n=15, mais il a aussi résisté à la vérification par la transformation d'Euler, qui relie les graphes généraux et connexes, et par une confirmation directe pour les petits types de cycles. Sa complexité est n à la puissance racine de n, bien en dessous de l'exponentielle, ce qui laisse une marge pour les prochains records.

Le kaléidoscope de symétries ne s'est pas contenté de mettre à jour l'encyclopédie OEIS. Il a montré comment les algorithmes « par évaporation » s'allient à la théorie des groupes, et a proposé un schéma universel pour d'autres classes de graphes — les graphes d'intervalles, les graphes cordaux bipartis, les graphes de comparabilité. À terme, on envisage le calcul distribué et un bond vers n=22. Et la métaphore des faisceaux diviseurs pourrait être utile dans les tests de modèles génératifs de réseaux ou dans des problèmes de chémoinformatique, où il faut énumérer des structures moléculaires non isomorphes.

Revenons au nombre 7 278 601 292 779 396 715. Derrière lui, il n'y a pas de chaos, mais une architecture rigoureuse de réflexions. Chaque combinaison d'arêtes se souvient de son orbite dans le labyrinthe des symétries, et ce labyrinthe peut désormais être parcouru sans perte.