Kaleidoscope of Symmetries: A New Record in Counting Chordal Graphs ✛
Context
Many structures—from molecules to social networks—are conveniently described by graphs. But when the names of vertices aren't important, only the connections between them, counting unlabeled objects comes to the fore. Chordal graphs, which lack induced cycles longer than three, are a central class in algorithmic graph theory. They model sparse hierarchical networks and underpin efficient algorithms. Despite decades of effort, the exact number of such graphs was known only up to 15 vertices. Further progress was hindered by the need to account for all possible symmetries—permutations that turn one drawing into another, indistinguishable without labels.
Methods
The central tool is Burnside's lemma: the number of unlabeled objects equals the average number of labeled objects fixed by each permutation from the symmetry group. For the group of all n! permutations, this reduces to a sum over cycle types. In 2021, Hebert-Johnson, Lokshtanov, and Vigoda proposed an efficient dynamic programming algorithm for counting labeled chordal graphs via an 'evaporation' process: repeatedly remove simplicial vertices (those whose neighbors form a clique) until the empty graph remains. The new approach adapts this evaporation to a world with symmetry, turning it into orbit evaporation: all vertices in one orbit evaporate simultaneously. The key insight is divisible bundle decomposition. If a permutation contains a cycle of length c, and a connected component spans several orbits, its structure decomposes into a bundle of d components, each symmetric under a smaller group of order c/d. This allows one to reduce the calculation to a recursive call of the same problem in a 'subworld' with diminished orbits. The result is a system of recurrence relations that computes the exact number of invariant chordal graphs for each cycle type. Implementing this computational method required careful programming and verification.
Results
Relying on this framework, the author computed both sequences—total and connected—up to n=20. For n=16, the number of all chordal graphs is 5 985 406 996 403; for n=17, 247 178 491 630 853; and for n=20, it reaches 7 278 601 292 779 396 715. Verification was carried out in four independent ways: complete agreement with previously known terms up to n=15; direct exhaustive confirmation for small cycle types; reproduction of the labeled limit; and—separately—a check via the Euler transform, linking the total and connected sequences. A theoretical estimate proved that the algorithm runs in subexponential time $n^{O(√n)}$—much faster than a general parameterized approach that would require single exponential.
Implications
This work does more than just update two rows in OEIS. It demonstrates that the 'evaporation' method is compatible with symmetry analysis, and it proposes a constructive scheme for other graph classes that admit similar decompositions. The connection between symmetry and invariants, so profound in physics, here receives a combinatorial embodiment. Divisible bundle decomposition essentially explains how high-order symmetry is assembled from repeating blocks of lower symmetry—and this may find applications far beyond chordal graphs, in any enumeration problem involving the action of cyclic groups.
Future development
Immediate prospects include extending the method to other graph classes, such as interval graphs or comparability graphs. The algorithm could possibly be improved for permutations with many small cycles, which currently take the lion's share of time. An intriguing reverse direction: could physical models that use evaporation (e.g., in statistical mechanics) benefit from combinatorial methods that account for symmetry?
Impact
The result will impact graph theory, combinatorics, and algorithm design. In particular, it provides benchmark data for testing generative network models and for applications requiring enumeration of non-isomorphic structures.
Next steps
The next step is formalizing conditions under which divisible bundle decomposition carries over to other classes, and implementing distributed computations to reach n=21 or 22.
Key open problems
The problem of enumerating unlabeled structures is a combinatorial analogue of understanding the phase space of complex systems. The connection to the graph isomorphism problem and to questions of efficiently accounting for symmetries makes this work relevant to fundamental problems in complexity theory and to applications in chemoinformatics, where one often needs to enumerate non-isomorphic molecular graphs.
The knowledge machine's view
This section is addressed to the author of the paper and their colleagues. Neighbouring works were found by meaning-based search across our archive, not by word overlap. We do not review: we show the field around the work.
What the work does
This paper introduces a new method for counting unlabeled chordal graphs, based on orbit evaporation and decomposition of split beams. The author computed the number of all and connected chordal graphs up to 20 vertices, verifying the results in several ways, and proved a subexponential running time bound.
Where its strength is
The strong point is the efficient adaptation of Burnside's lemma to the class of chordal graphs via orbit evaporation, which significantly pushed the computational boundaries. The decomposition of split beams provides a recursive reduction that opens the way for further generalizations.
Where it could go next
- It might be interesting to explore the connection with graph compression algorithms: in our archive, there is a paper on edge contractions that preserve key properties. Perhaps orbit evaporation techniques could suggest new invariants for compressed representations.based on: Compressing networks: when roads become points arXiv:2607.14834
- There is a paper nearby on communities in networks assembled like a puzzle; one could try applying chordal graph counting to analyze typical structures in such communities.based on: Communities by Size: When Networks Assemble Like a Puzzle arXiv:2605.25248
- The archive contains an analysis of monodromy in vineyards, studying symmetries and branched coverings; perhaps methods from that area could provide a topological perspective on symmetries of chordal graphs.based on: Monodromy in Vineyards: Blame It on One Singularity arXiv:2607.01046
Worth trying
- Investigate whether orbit evaporation yields a faster isomorphism test for chordal graphs.
- Apply split beam decomposition to other graph classes with similar properties, such as interval graphs.
- Use the computed sequences to refine the asymptotics of the number of chordal graphs.
Why this may matter
Exact counts of unlabeled structures are important for understanding typical properties of networks and may find applications in chemistry, bioinformatics, and social network analysis.
Nearby works in our archive
- The Secret of Warped Webs: A New Way to Compare Networkssimilarity 0.60
- Mini-brains learn to ignore repeated stimulisimilarity 0.59
- Compressing networks: when roads become pointssimilarity 0.59
- Quantum Knots from Particle Trajectoriessimilarity 0.59
- Communities by Size: When Networks Assemble Like a Puzzlesimilarity 0.59
- Monodromy in Vineyards: Blame It on One Singularitysimilarity 0.58
The archive is sparse around this work: the closest review is only 0.60, against a usual 0.64. It looks like few have drilled nearby.
Original abstract
as written by the authors 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.
If each chordal graph on 20 vertices took up one byte, their total volume would exceed 7 petabytes — more than all the data stored in the largest data centers.
The idea of enumerating all possible structures is taken to the extreme in Borges' 'The Library of Babel,' where all conceivable books are stored. Counting chordal graphs is a step toward inventorying one of the 'shelves' of such a library in the world of discrete forms.
Key numbers
- number of chordal graphs at n=20: 7.2786 × 1015
- previous record n: 15
- number of new sequence terms: 5 (n=16–20)
- algorithm complexity: n^{O(√n)}
- number of cycle types at n=20 (number of terms in the Burnside sum): 627