Kaléidoscope de symétries : un nouveau record dans le dénombrement des graphes cordaux ✛
Contexte
De nombreuses structures, des molécules aux réseaux sociaux, se décrivent commodément par des graphes. Mais lorsque seuls comptent les liens entre sommets et non leurs noms, l'énumération des objets non étiquetés devient primordiale. Les graphes cordaux, qui ne contiennent aucun cycle induit de longueur supérieure à trois, constituent une classe centrale en théorie algorithmique des graphes. Ils modélisent des réseaux hiérarchiques épars et sont à la base d'algorithmes efficaces. Malgré des décennies d'efforts, le nombre exact de tels graphes n'était connu que jusqu'à 15 sommets. Pour aller plus loin, il fallait tenir compte de toutes les symétries possibles — les permutations qui transforment un dessin en un autre, indistinguable sans étiquettes.
Méthodes
L'outil central est le lemme de Burnside : le nombre d'objets non étiquetés est égal à la moyenne du nombre d'objets étiquetés fixes sous chaque permutation du groupe de symétries. Pour le groupe de toutes les n! permutations, cela se réduit à une somme sur les types de cycles. En 2021, Hebert-Johnson, Lokhtanov et Vigoda ont proposé un algorithme dynamique efficace pour compter les graphes cordaux étiquetés via un processus d'« évaporation » : on retire itérativement les sommets simpliciaux (dont les voisins forment une clique) jusqu'à obtenir un graphe vide. La nouvelle approche adapte cette évaporation au monde symétrique, la transformant en évaporation orbitale : tous les sommets d'une même orbite s'évaporent simultanément. La découverte clé est la décomposition en faisceaux diviseurs. Si une permutation contient un cycle de longueur c et qu'une composante connexe couvre plusieurs orbites, sa structure se décompose en un faisceau de d composantes, chacune symétrique sous un groupe plus petit d'ordre c/d. Cela permet de ramener le calcul à un appel récursif du même problème dans un « sous-monde » avec des orbites réduites. On construit ainsi un système de relations de récurrence qui calcule le nombre exact de graphes cordaux invariants pour chaque type de cycles. L'implémentation de cette méthode de calcul a exigé une programmation soignée et des vérifications.
Résultats
En s'appuyant sur cet appareil, l'auteur a calculé les deux suites — générale et connexe — jusqu'à n=20. Pour n=16, le nombre total de graphes cordaux est 5 985 406 996 403 ; pour n=17, il est 247 178 491 630 853 ; et pour n=20, il atteint 7 278 601 292 779 396 715. La vérification a été effectuée de quatre manières indépendantes : correspondance exacte avec les termes connus jusqu'à n=15 ; confirmation par force brute pour les petits types de cycles ; reproduction de la limite étiquetée ; et, séparément, vérification via la transformation d'Euler reliant les suites générale et connexe. L'estimation théorique a prouvé que l'algorithme fonctionne en temps sous-exponentiel $n^{O(√n)}$ — bien plus rapide que l'approche paramétrée générale qui aurait exigé une exponentielle simple.
Implications
Ce travail ne se contente pas de mettre à jour deux lignes dans l'OEIS. Il démontre que la méthode par « évaporation » est compatible avec l'analyse des symétries et propose un schéma constructif pour d'autres classes de graphes admettant de telles décompositions. Le lien entre symétrie et invariants, si profond en physique, trouve ici une incarnation combinatoire. La décomposition en faisceaux diviseurs explique, en substance, comment une symétrie d'ordre élevé s'assemble à partir de blocs répétés de symétrie plus faible — et cela pourrait trouver des applications bien au-delà des graphes cordaux, dans tout problème d'énumération avec action de groupes cycliques.
Développements futurs
Les perspectives immédiates incluent l'extension de la méthode à d'autres classes de graphes, comme les graphes d'intervalles ou les graphes de comparabilité. On pourrait aussi améliorer l'algorithme pour traiter les permutations ayant beaucoup de petites orbites, qui actuellement prennent la part du lion du temps. Une direction inverse est également intéressante : les modèles physiques qui utilisent l'évaporation (par exemple en mécanique statistique) pourraient-ils bénéficier des méthodes combinatoires prenant en compte la symétrie ?
Impact
Le résultat influencera la théorie des graphes, la combinatoire et la conception d'algorithmes. En particulier, il fournit des données de référence pour tester les modèles génératifs de réseaux et pour les applications nécessitant l'énumération de structures non isomorphes.
Prochaines étapes
La prochaine étape consiste à formaliser les conditions sous lesquelles la décomposition en faisceaux diviseurs se transpose à d'autres classes, et à mettre en œuvre des calculs distribués pour atteindre n=21 ou 22.
Problèmes ouverts clés
Le problème de l'énumération des structures non étiquetées est un analogue combinatoire de la compréhension de l'espace des phases des systèmes complexes. Le lien avec le problème de l'isomorphisme de graphes et avec les questions de prise en compte efficace des symétries rend ce travail pertinent pour les problèmes fondamentaux de la théorie de la complexité et pour des applications en chémoinformatique, où l'on doit souvent énumérer des graphes moléculaires non isomorphes.
Le regard de la machine du savoir
Cette section s'adresse à l'auteur du travail et à ses collègues. Les travaux voisins ont été trouvés par une recherche sémantique dans notre archive, et non par correspondance de mots. Nous n'évaluons pas : nous montrons le champ autour.
Ce que fait ce travail
Cet article présente une nouvelle méthode pour compter les graphes cordaux non étiquetés, basée sur l'évaporation orbitale et la décomposition des faisceaux diviseurs. L'auteur a calculé le nombre de tous les graphes cordaux, ainsi que celui des graphes cordaux connexes, jusqu'à 20 sommets, en vérifiant les résultats par plusieurs méthodes, et a prouvé une estimation sous-exponentielle du temps d'exécution.
Où est sa force
La force de ce travail réside dans l'adaptation efficace du lemme de Burnside à la classe des graphes cordaux via l'évaporation orbitale, ce qui a permis de repousser considérablement les limites du calcul. La décomposition des faisceaux diviseurs fournit une réduction récursive qui ouvre la voie à d'autres généralisations.
Vers où avancer
- Il pourrait être intéressant d'examiner le lien avec les algorithmes de compression de graphes : dans nos archives, il y a un travail voisin sur la contraction d'arêtes préservant les propriétés clés. Peut-être que la technique d'évaporation orbitale suggérera de nouveaux invariants pour les représentations compressées.appui : Compresser les réseaux : quand les routes deviennent des points arXiv:2607.14834
- À côté, il y a un travail sur les communautés dans les réseaux assemblés comme un puzzle ; on pourrait essayer d'appliquer le dénombrement des graphes cordaux pour analyser les structures typiques de ces communautés.appui : Communautés sur mesure : quand les réseaux s'assemblent comme un puzzle arXiv:2605.25248
- Les archives contiennent une analyse sur la monodromie dans les vignobles, où l'on étudie les symétries et les revêtements ramifiés ; il est possible que les méthodes de ce domaine aident à examiner les symétries des graphes cordaux d'un point de vue topologique.appui : Monodromie dans les vignobles : une seule singularité en cause arXiv:2607.01046
À essayer
- Vérifier si l'évaporation orbitale offre un moyen plus rapide de tester l'isomorphisme pour les graphes cordaux.
- Appliquer la décomposition des faisceaux diviseurs à d'autres classes de graphes présentant des propriétés similaires, comme les graphes d'intervalles.
- Utiliser les séquences calculées pour affiner l'asymptotique du nombre de graphes cordaux.
Pourquoi cela peut compter
Les dénombrements exacts de structures non étiquetées sont importants pour comprendre les propriétés typiques des réseaux et peuvent trouver des applications en chimie, en bioinformatique et dans l'analyse des réseaux sociaux.
Travaux voisins dans notre archive
- Le secret des nœuds courbes : comment comparer les toiles d'araignéeproximité 0.60
- Les mini-cerveaux apprennent à ignorer les stimuli répétésproximité 0.59
- Compresser les réseaux : quand les routes deviennent des pointsproximité 0.59
- Nœuds quantiques tissés par les trajectoires des particulesproximité 0.59
- Communautés sur mesure : quand les réseaux s'assemblent comme un puzzleproximité 0.59
- Monodromie dans les vignobles : une seule singularité en causeproximité 0.58
L'archive est vide autour de ce travail : l'analyse la plus proche n'est qu'à 0.60, contre 0,64 d'ordinaire. Il semble qu'on ait peu foré à côté.
Résumé original
tel que rédigé par les auteurs, en anglais arXiv:2607.02613
We compute the number of unlabeled chordal graphs on $$n$$ vertices, both the total count (OEIS A048193) and the connected count (OEIS A048192), extending two sequences whose published values had remained at $$n=15$$. The method is a Polya-Burnside enumeration: the number of unlabeled graphs in a class closed under relabeling is the average over $$S_n$$ of the number of labeled graphs fixed by each permutation. The technical core is the evaluation, for an arbitrary permutation $$\pi$$, of the number of $$\pi$$-invariant labeled chordal graphs. We give a dynamic program for this quantity that lifts the evaporation-based labeled chordal counting of Hebert-Johnson, Lokshtanov and Vigoda to the equivariant setting. Its central structural ingredient is a divisor-bundle decomposition: when a connected piece spans a cyclic orbit of size $$c$$, it forms, for each divisor $$d \mid c$$, a $$d$$-fold bundle whose constituent is an object of the same kind in the cyclic world of order $$c/d$$, computed by the same program recursively. We prove the decomposition and the correctness of the resulting recurrences, and we prove that the full Burnside computation runs in sub-exponential time $$n^{O(\sqrt{n})}$$. We report the new terms through $$n=20$$ and describe four independent validations, including exact agreement with all previously known values of both sequences and an Euler-transform consistency check.
Si chaque graphe cordal à 20 sommets occupait un octet, leur volume total dépasserait 7 pétaoctets — plus que toutes les données stockées dans les plus grands centres de données.
L'idée d'énumérer toutes les structures possibles est poussée à l'extrême dans la « Bibliothèque de Babel » de Borges, où sont conservés tous les livres imaginables. Compter les graphes cordaux, c'est faire un pas vers l'inventaire d'une des « étagères » d'une telle bibliothèque dans le monde des formes discrètes.
Chiffres clés
- nombre de graphes cordaux pour n=20: 7.2786 × 1015
- n record précédent: 15
- nombre de nouveaux termes des suites: 5 (n=16–20)
- complexité de l'algorithme: n^{O(√n)}
- nombre de types de cycles pour n=20 (nombre de termes dans la somme de Burnside): 627