Kaleidoscope of Symmetries: A New Record in Counting Chordal Graphs ✛
7 278 601 292 779 396 715. That’s exactly how many unlabeled chordal graphs, graphs with no induced cycles of length four or more, can be built on twenty vertices. This number isn’t a puzzle for a supercomputer; it’s the exact output of a new algorithm that treats symmetry as a tool, not an obstacle.
Imagine a kaleidoscope: a few colored beads generate an infinite pattern, multiplied by mirrors. In the enumeration of unlabeled graphs (where vertices are indistinguishable), symmetries act as those mirrors: permutations of vertices that leave the graph unchanged. To count all unlabeled graphs, you must account for every possible reflection. That’s where Burnside’s lemma comes in: the average over all permutations of the number of graphs fixed by a given permutation equals the desired count. The trouble is, there are factorial-many permutations — for n=20, that’s 2.43×$10^{18}$ possibilities. But the algorithm sidesteps this avalanche by leaning on ‘evaporation’.
Evaporation is an elegant process: from a chordal graph, repeatedly remove simplicial vertices (those whose neighbors form a clique) until an empty graph remains. In 2021, an approach equal parts von Neumann and dynamic programming made fast work of counting labeled chordal graphs. But how to transplant it into the world of symmetries? The answer: let whole orbits, groups of vertices mapped to each other by the permutation, evaporate at once. Thus orbital evaporation is born.
The trickiest bit is when an orbit is heterogeneous, its parts linked by complex bridges. That’s where the divisible-bundle decomposition comes in. If the permutation contains a cycle of length c, and a connected component of the graph sprawls across several orbits, it breaks into d identical ‘bundles,’ each symmetric under a smaller group, as if the kaleidoscope reflected only a portion of the bead, not the whole. This trick reduces the computation to a recursive call of the same problem in a miniaturized world: instead of the original group, you work with a group d times smaller. The recursion underpins a computational scheme that systematically iterates over cycle types and accumulates contributions.
Thus, step by step, they reached n=20. Not only did the algorithm match previously known values up to n=15, but it also passed the test via Euler-transformation that links total and connected graphs, as well as direct verification for small cycle types. Its complexity is n to the power of the square root of n, far sub-exponential, leaving headroom for the next records.
The kaleidoscope of symmetries hasn’t merely updated the OEIS. It has demonstrated how ‘evaporation’ algorithms get along with group theory, and has offered a universal scheme for other graph classes — interval graphs, chordal bipartite graphs, comparability graphs. On the horizon: distributed computing and a push to n=22. And the divisible-bundle metaphor may come in handy for testing generative models of networks or in cheminformatics tasks that involve sifting through non-isomorphic molecular structures.
Let’s return to the number 7 278 601 292 779 396 715. Behind it lies not chaos, but an austere architecture of reflections. Every edge-set recalls its orbit in the hall of mirrors of symmetries, and now that hall can be traversed without loss.
For n=20, one had to iterate over 627 distinct cycle types: each contributes its own term to Burnside's sum.
The idea of enumerating all possible structures is taken to the limit in Borges's 'Library of Babel,' which houses every conceivable book. Counting chordal graphs is a step toward cataloging one of the 'shelves' in that library for the world of discrete forms.