Калейдоскоп симметрий: новый рекорд в подсчёте хордальных графов ✛

Оригинальная аннотация

как её написали авторы, на английском 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.