CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs
Alexander Chervov ⋅ Dmytro Fedoriaka ⋅ Mark Obozov ⋅ Elena Konstantinova ⋅ Anton Naumov ⋅ Igor Kiselev ⋅ Anastasia Sheveleva ⋅ Ivan Koltsov ⋅ Sergei Lytkin ⋅ Andrei Smolensky ⋅ Alexander Soibelman ⋅ Fedor Levkovich-Maslyuk ⋅ Ruslan Grimov ⋅ Dmitry Volovich ⋅ Artem Isakov ⋅ Anton Kostin ⋅ Michael Litvinov ⋅ Nick Vilkin-Krom ⋅ Alim Bidzhiev ⋅ Artem Krasnyi ⋅ Mikhail Evseev ⋅ Elizaveta Geraseva ⋅ Liliya Grunwald ⋅ Sergey Galkin ⋅ Eduard Koldunov ⋅ Stanislav Diner ⋅ Artem Chevychelov ⋅ Evelina Kudasheva ⋅ Arsenii Sychev ⋅ Zakhar Kogan ⋅ Altana Natyrova ⋅ Lidia Shishina ⋅ Lyudmila Cheldieva ⋅ Vladislav Zamkovoy ⋅ Dmitrii Kovalenko ⋅ Oleg Papulov ⋅ Kudashev Sergey ⋅ Dmitry Shiltsov ⋅ Rustem Turtayev ⋅ Olga Nikitina ⋅ Dariya Mamayeva ⋅ Nikolenko Sergei ⋅ Anton Titarenko ⋅ Antonina Dolgorukova ⋅ Alexey Aparnev ⋅ Orianne Debeaupuis ⋅ Simo Alami ⋅ Herve Isambert
Abstract
We present the first public release of CayleyPy, an open-source Python library for working with Cayley and Schreier graphs. Compared to classical systems such as GAP and Sage, CayleyPy scales to much larger graphs and achieves speedups of several orders of magnitude. Using CayleyPy we obtained about 200 new conjectures on diameters and growth of Cayley and Schreier graphs. For symmetric groups $S_n$ we observe quasi-polynomial diameter formulas depending on $n \bmod s$, and conjecture this is a general phenomenon. This leads to efficient diameter computation despite NP-hardness in general. We refine Babai-type bounds for $S_n$, proposing $\tfrac12 n^2 + 4n$ as an upper bound in the standard case, and identify explicit generator families likely maximizing diameters, confirmed for $n \leq 15$. We also conjecture a closed formula for the diameter of the directed Cayley graph generated by the left cyclic shift and $(1,2)$, answering a 1968 question of V.,M.~Glushkov. For nilpotent groups we conjecture linear dependence of diameters on $p$ in $\operatorname{UT}_n(\mathbb{Z}/p\mathbb{Z})$, improving results of Ellenberg, and observe Gaussian-type growth distributions akin to Diaconis’ results for $S_n$. Several conjectures are LLM-friendly, reducible to sorting problems verifiable via Python code. To foster benchmarking, we release 10+ Kaggle datasets for path-finding on Cayley graphs. CayleyPy supports arbitrary permutation and matrix groups with 100+ predefined generators, including puzzle groups. Its growth computation routines outperform GAP/Sage by up to 1000× in both speed and capacity.
Chat is not available.
Successful Page Load