Le secret du kaléidoscope : un record dans le comptage des réseaux invisibles ✛

Original: "Counting Unlabeled Chordal Graphs by Equivariant Evaporation"
· Matthew Sun
arXiv:2607.02613 · 2026-07-01 · CC BY 4.0 · 2 min
Une nouvelle méthode permet de connaître rapidement le nombre exact de réseaux particuliers construits à partir de points identiques.

Imaginez un kaléidoscope : une poignée de petits verres colorés, réfléchis par des miroirs, engendre d'innombrables motifs. En mathématiques, on doit souvent recenser les réseaux possibles formés de points identiques — par exemple, toutes les façons de les relier par des lignes, si les points ne peuvent pas être étiquetés. L'énumération directe est ici impuissante : pour 20 points, il y a plus de possibilités que d'étoiles dans la galaxie.

Il existe pourtant une astuce élégante. Au lieu d'énumérer tous les motifs, on utilise une moyenne sur toutes les rotations possibles (permutations des points). Pour chaque rotation, on regarde combien de motifs restent inchangés, puis on prend la moyenne. On obtient ainsi le nombre exact. Mais le nombre de rotations est lui aussi énorme — la décomposition en parties identiques aide. Si un motif est symétrique, il est constitué de morceaux répétés. En remarquant cela, les mathématiciens ont appliqué une approche récursive : le problème se réduisait à compter ces morceaux, beaucoup plus rapidement. Le kaléidoscope se replie sur lui-même.

Si l'on tentait d'écrire chaque motif possible sur 20 points avec un octet, il faudrait plus de sept pétaoctets — c'est plus que toutes les données des plus grands centres de données du monde.

Ainsi, pour la première fois, on a pu compter exactement le nombre de motifs pour 16, 17, 18, 19 et 20 points. Le résultat pour 20 points est un nombre colossal : 7 278 601 292 779 396 715. Derrière ce nombre, il n'y a pas de chaos, mais une architecture ordonnée de réflexions. La méthode ne servira pas seulement pour des motifs purs, mais aussi pour l'énumération de médicaments et de nouveaux matériaux, et elle pourrait accélérer l'apprentissage automatique dans la recherche de meilleures configurations de réseaux de neurones.

La symétrie préserve quelque chose de fondamental : en physique, les lois de conservation ; en combinatoire, l'ordre du comptage. Le théorème de Emmy Noether inspire cette astuce.

Pour compter toutes les variantes pour 20 points, il a fallu prendre en compte 627 types de symétrie différents.

L'idée d'énumérer toutes les structures possibles rappelle la « Bibliothèque de Babel » de Borges — un livre contenant tous les livres imaginables.

a(n) = \frac{1}{n!} \sum_{\pi \in S_n} \mathrm{fix}(\pi)
le nombre d'objets non étiquetés est égal à la moyenne du nombre d'objets étiquetés invariants sous chaque permutation
\mathrm{BUNDLE}(\mu) = \mathrm{cfix}(\mu) + \sum_{d>1,\, d\mid\gcd(\mu)} d^{|\mu|-1} \mathrm{cfix}^{\langle N/d \rangle}(\mu/d)
une composante en faisceau soit n'a pas de symétrie interne, soit se décompose en d copies plus petites avec une multiplicité d^{|μ|-1}
Scientifiques
Emmy Noether
Notions
graphes