@misc{oeis, author = {{OEIS Foundation Inc.}}, title = {{A186783}: Diameter of the symmetric group {$S_n$} when generated by the transposition {$(1,2)$} and both left and right rotations by {$(1,2,\ldots,n)$}}, year = {2026}, howpublished = {The On-Line Encyclopedia of Integer Sequences}, note = {Entry created by Tony Bartoletti in 2011; accessed 4 November 2026}, url = {https://oeis.org/A186783} } @misc{antiufeev, author = {Antiufeev, Grigorii}, title = {A Lower Bound for the Diameter of Cayley Graph of the Symmetric Group {$S_n$} Generated by {$(12)$}, {$(12\dots n)$}, {$(1n\dots2)$}}, year = {2026}, howpublished = {arXiv:2601.08715v3 [math.CO]}, note = {Version 3, 4 June 2026; Theorem 2}, url = {https://arxiv.org/abs/2601.08715v3} } @misc{cayleypy, author = {Chervov, A. and Obozov, M. and Soibelman, A. and Lytkin, S. and others}, title = {{CayleyPy RL}: Pathfinding and Reinforcement Learning on {Cayley} Graphs}, year = {2026}, howpublished = {arXiv:2502.18663v3 [cs.LG]}, note = {First submitted in 2025; version 3, 15 May 2026; Sections 4.1--4.3}, url = {https://arxiv.org/abs/2502.18663v3} } @article{bjorner-brenti, author = {Bj{\"o}rner, Anders and Brenti, Francesco}, title = {Affine Permutations of Type {$A$}}, journal = {The Electronic Journal of Combinatorics}, volume = {3}, number = {2}, pages = {R18}, year = {1996}, note = {Propositions 3.1 and 3.3, pp. 6--8}, doi = {10.37236/1276}, url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i2r18} } @article{diaconis-graham, author = {Diaconis, Persi and Graham, R. L.}, title = {Spearman's Footrule as a Measure of Disarray}, journal = {Journal of the Royal Statistical Society. Series B (Methodological)}, volume = {39}, number = {2}, pages = {262--268}, year = {1977}, note = {Theorem 2, pp. 264--266}, doi = {10.1111/j.2517-6161.1977.tb01624.x}, url = {https://mathweb.ucsd.edu/~ronspubs/77_04_spearmans.pdf} } @book{coxeter, author = {Bj{\"o}rner, Anders and Brenti, Francesco}, title = {Combinatorics of {Coxeter} Groups}, series = {Graduate Texts in Mathematics}, volume = {231}, publisher = {Springer}, year = {2005}, doi = {10.1007/3-540-27596-7}, url = {https://link.springer.com/book/10.1007/3-540-27596-7}, note = {Proposition 1.4.7, Corollary 1.4.8, Proposition 1.5.2, Theorems 2.1.5 and 2.2.2, Corollary 2.2.5, Propositions 2.2.7 and 2.3.1} } @article{harary-kabell, author = {Harary, Frank and Kabell, Jerald A.}, title = {Counting Balanced Signed Graphs Using Marked Graphs}, journal = {Proceedings of the Edinburgh Mathematical Society}, volume = {24}, number = {2}, pages = {99--104}, year = {1981}, doi = {10.1017/S0013091500006398}, note = {Structure Theorem for Balance, Section 1, p. 99} } @misc{majorization, author = {Nathanson, Melvyn B.}, title = {The {Muirhead--Rado} Inequality, 1: Vector Majorization and the Permutohedron}, howpublished = {arXiv:2109.01746v3 [math.CO]}, year = {2024}, note = {Version 3, 5 May 2024; Section 3 and Theorem 7}, url = {https://arxiv.org/abs/2109.01746v3} } @article{median, author = {Schwertman, Neil C. and Gilks, A. J. and Cameron, J.}, title = {A Simple Noncalculus Proof That the Median Minimizes the Sum of the Absolute Deviations}, journal = {The American Statistician}, volume = {44}, number = {1}, pages = {38--39}, year = {1990}, doi = {10.1080/00031305.1990.10475690}, url = {https://tommasorigon.github.io/StatI/approfondimenti/Schwertman1990.pdf} } @book{balance-proof, author = {Easley, David and Kleinberg, Jon}, title = {Networks, Crowds, and Markets: Reasoning About a Highly Connected World}, publisher = {Cambridge University Press}, year = {2010}, note = {Section 5.2, pp. 123--126: Balance Theorem and proof}, url = {https://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch05.pdf} } @article{berman-tenner, author = {Berman, Yosef and Tenner, Bridget Eileen}, title = {Pattern-Functions, Statistics, and Shallow Permutations}, journal = {The Electronic Journal of Combinatorics}, volume = {29}, number = {4}, pages = {P4.43}, year = {2022}, note = {Definition 2, Corollaries 25 and 31; journal numbering}, doi = {10.37236/10858}, url = {https://www.combinatorics.org/ojs/index.php/eljc/article/view/v29i4p43} } @article{depth, author = {Petersen, T. Kyle and Tenner, Bridget Eileen}, title = {The Depth of a Permutation}, journal = {Journal of Combinatorics}, volume = {6}, number = {1--2}, pages = {145--178}, year = {2015}, doi = {10.4310/joc.2015.v6.n1.a9}, note = {Theorem 1.1, Remark 1.2, Proposition 3.2; arXiv:1202.4765v3, 19 August 2014}, url = {https://arxiv.org/abs/1202.4765v3} } @unpublished{GuerrieriInPreparation, author = {Guerrieri, Andrea}, note = {In preparation} } @article{glushkov1968, author = {Glushkov, V. M.}, title = {Completeness of a system of operations in digital computers}, journal = {Cybernetics}, volume = {4}, number = {2}, pages = {1--4}, year = {1968}, doi = {10.1007/BF01073731}, note = {Translated from Kibernetika 4(2) (1968), 1--5} } @article{pogorelov1973, author = {Pogorelov, B. A.}, title = {A problem of {V. M. Glushkov}}, journal = {Cybernetics}, volume = {9}, pages = {895--899}, year = {1973}, doi = {10.1007/BF01069732}, note = {Translated from Kibernetika (1973), no.~5, 141--143} } @incollection{glukhov-zubov, author = {Glukhov, M. M. and Zubov, A. Yu.}, title = {On the lengths of symmetric and alternating permutation groups in various generating systems (a survey)}, booktitle = {Matematicheskie Voprosy Kibernetiki}, volume = {8}, pages = {5--32}, publisher = {Nauka}, address = {Moscow}, year = {1999}, note = {In Russian}, url = {https://keldysh.ru/papers/1999/mvk/mvk1999_5.pdf} } @misc{oeis-lx, author = {{OEIS Foundation Inc.}}, title = {{A039745}: Diameter of symmetric group {$S_n$} when generated by {$(1,2)$} and {$(1,2,3,\ldots,n)$}}, year = {2026}, howpublished = {The On-Line Encyclopedia of Integer Sequences}, note = {Entry by D. desJardins; accessed 5 November 2026}, url = {https://oeis.org/A039745} } @misc{cayleypy-growth, author = {Chervov, A. and Fedoriaka, D. and Konstantinova, E. and Naumov, A. and others}, title = {{CayleyPy Growth}: Efficient growth computations and hundreds of new conjectures on {Cayley} graphs (Brief version)}, year = {2026}, howpublished = {arXiv:2509.19162v2 [math.CO]}, note = {First submitted in 2025; version 2, 1 April 2026; Conjecture 11}, url = {https://arxiv.org/abs/2509.19162v2} } @misc{lx-hexagon, author = {Uskov, Sergei and Chervov, Alexander and Levkovich-Maslyuk, Fedor and Litvak, Ivan and Smolensky, Andrei and Soibelman, Alexander}, title = {Exact diameter of the symmetric group with {LX} generators}, year = {2026}, howpublished = {Hexagon preprint hexagon:2611.00039v1}, note = {Version 1, 3 November 2026}, url = {https://hexagonmath.org/2611.00039v1} } @misc{lx-lean, author = {Uskov, S. and Chervov, A. and Levkovich-Maslyuk, F. and Litvak, I. and Smolensky, A. and Soibelman, A.}, title = {Exact directed {L/X} diameter in {Lean}~4}, year = {2026}, howpublished = {GitHub repository, release v1.0.0}, note = {Commit 9e04062; Lean 4.34.0, Mathlib v4.34.0}, url = {https://github.com/snow-ghost/glushkov-lx-lean/releases/tag/v1.0.0} } @article{BabaiSeress1988, author = {Babai, L. and Seress, {\'A}.}, title = {On the diameter of {Cayley} graphs of the symmetric group}, journal = {Journal of Combinatorial Theory, Series A}, volume = {49}, number = {1}, pages = {175--179}, year = {1988}, doi = {10.1016/0097-3165(88)90033-7} } @article{BabaiSeress1992, author = {Babai, L. and Seress, {\'A}.}, title = {On the diameter of permutation groups}, journal = {European Journal of Combinatorics}, volume = {13}, number = {4}, pages = {231--243}, year = {1992}, doi = {10.1016/S0195-6698(05)80029-0} } @inproceedings{BabaiBealsSeress2004, author = {Babai, L. and Beals, R. and Seress, {\'A}.}, title = {On the diameter of the symmetric group: polynomial bounds}, booktitle = {Proceedings of the Fifteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA} 2004)}, publisher = {SIAM}, pages = {1108--1112}, year = {2004} } @article{BreuillardGreenTao2011, author = {Breuillard, E. and Green, B. and Tao, T.}, title = {Approximate subgroups of linear groups}, journal = {Geometric and Functional Analysis}, volume = {21}, number = {4}, pages = {774--819}, year = {2011}, doi = {10.1007/s00039-011-0122-y} } @article{HelfgottSeress2014, author = {Helfgott, H. A. and Seress, {\'A}.}, title = {On the diameter of permutation groups}, journal = {Annals of Mathematics}, volume = {179}, number = {2}, pages = {611--658}, year = {2014}, doi = {10.4007/annals.2014.179.2.4} } @inproceedings{CayleyPyCube2025, author = {Alexander Chervov and Kirill Khoruzhii and Nikita Bukhal and Jalal Naghiyev and Vladislav Zamkovoy and Ivan Koltsov and Lyudmila Cheldieva and Arsenii Sychev and Arsenii Lenin and Mark Obozov and Egor Urvanov and Alexey M. Romanov}, title = {A Machine Learning Approach That Beats Rubik's Cubes}, booktitle = {Advances in Neural Information Processing Systems}, volume = {38}, pages = {191182--191204}, year = {2025}, doi = {10.52202/085713-5741} } @article{CayleyPyHolography2026, author = {A. Chervov and F. Levkovich-Maslyuk and A. Smolensky and F. Khafizov and I. Kiselev and D. Melnikov and I. Koltsov and S. Kudashev and D. Shiltsov and M. Obozov and S. Krymskii and V. Kirova and E. V. Konstantinova and A. Soibelman and S. Galkin and L. Grunwald and A. Kotov and A. Alexandrov and S. Lytkin and D. Fedoriaka and A. Chevychelov and Z. Kogan and A. Natyrova and L. Cheldieva and O. Nikitina and S. Fironov and A. Vakhrushev and A. Lukyanenko and V. Ilin and D. Gorodkov and N. Bogachev and I. Gaiur and M. Zaitsev and F. Petrov and L. Petrov and T. Gaintseva and A. Gavrilova and M. N. Smirnov and N. Kalinin and A. Khan and K. Jung and H. Mousset and H. Isambert and O. Debeaupuis}, title = {{CayleyPy-4}: {AI}-Holography. Towards Analogs of Holographic String Dualities for {AI} Tasks}, year = {2026}, eprint = {2603.22195}, archivePrefix = {arXiv}, primaryClass = {hep-th}, url = {https://arxiv.org/abs/2603.22195} } @article{DouglasFraserTaliente2025, author = {Michael R. Douglas and Kit Fraser-Taliente}, title = {Diffusion Models for Cayley Graphs}, year = {2025}, eprint = {2503.05558}, archivePrefix = {arXiv}, primaryClass = {cs.LG} } % ============================================================ % DeepCube / Rubik's-cube ML % ============================================================ @inproceedings{McAleerEtAl2019DeepCube, author = {Stephen McAleer and Forest Agostinelli and Alexander Shmakov and Pierre Baldi}, title = {Solving the Rubik's Cube with Approximate Policy Iteration}, booktitle = {International Conference on Learning Representations}, year = {2019} } @article{AgostinelliEtAl2019DeepCubeA, author = {Forest Agostinelli and Stephen McAleer and Alexander Shmakov and Pierre Baldi}, title = {Solving the Rubik's Cube with Deep Reinforcement Learning and Search}, journal = {Nature Machine Intelligence}, volume = {1}, number = {8}, pages = {356--363}, year = {2019}, doi = {10.1038/s42256-019-0070-z} } @article{Takano2023EfficientCube, author = {Kyo Takano}, title = {Self-Supervision is All You Need for Solving Rubik's Cube}, journal = {Transactions on Machine Learning Research}, year = {2023}, eprint = {2106.03157}, archivePrefix = {arXiv} } @inproceedings{Johnson2018RubiksGuidance, author = {Colin G. Johnson}, title = {Solving the Rubik's Cube with Learned Guidance Functions}, booktitle = {2018 IEEE Symposium Series on Computational Intelligence (SSCI)}, pages = {2082--2089}, year = {2018}, doi = {10.1109/SSCI.2018.8628626} } @article{HeYau2022, author = {He, Yang-Hui and Yau, Shing-Tung}, title = {Graph Laplacians, Riemannian Manifolds and their Machine-Learning}, journal = {Mathematics, Computation and Geometry of Data}, volume = {2}, number = {1}, pages = {1--48}, year = {2022}, doi = {10.4310/MCGD.2022.v2.n1.a1}, eprint = {2006.16619}, archivePrefix = {arXiv}, primaryClass = {math.CO} } % ============================================================ % Other recent ML + Cayley/group-graph papers % ============================================================ @article{BarketEtAl2026CayleyGraphs, author = {Rashid Barket and Enrico Grimaldi and Yacoub Hendi and Edward Hirst and Adam Onus and Harmeet Singh}, title = {Learning the Graphical Nature of Symmetries}, year = {2026}, eprint = {2607.12026}, archivePrefix = {arXiv}, primaryClass = {stat.ML} } @misc{lrxformalization, author = {Uskov, S. and Chervov, A. and Levkovich-Maslyuk, F. and Litvak, I. and Smolensky, A. and Soibelman, A.}, title = {Exact directed {L/X} diameter in {Lean}~4}, howpublished = {\url{https://github.com/snow-ghost/lrx-lean/releases/tag/v1.0.0}}, note = {Lean 4 formalization, version v1.0.0, commit \texttt{9e04062}}, year = {2026}, month = nov }