% references.bib -- BibTeX version of the bibliography of main.tex
% Keys are identical to those used in \cite{...} in main.tex.

%======================================================================
% Historical work on Glushkov's problem
%======================================================================

@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    = {English translation of Kibernetika \textbf{4}(2) (1968), 1--5}
}

@article{pogorelov1973,
  author  = {Pogorelov, B. A.},
  title   = {On a problem of {V.~M. Glushkov}},
  journal = {Kibernetika},
  number  = {5},
  pages   = {141--143},
  year    = {1973},
  note    = {In Russian. English translation: \emph{A problem of V.~M. Glushkov},
             Cybernetics \textbf{9} (1973), 895--899,
             \href{https://doi.org/10.1007/BF01069732}{doi:10.1007/BF01069732}.
             Historical results and this bibliographic record are also
             given in~\cite[pp.~20--21 and reference~48]{glukhovzubov1999}}
}

@incollection{glukhovzubov1999,
  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},
  publisher = {Nauka},
  address   = {Moscow},
  pages     = {5--32},
  year      = {1999},
  url       = {https://keldysh.ru/papers/1999/mvk/mvk1999_5.pdf},
  note      = {In Russian}
}

@incollection{zubov1998,
  author    = {Zubov, A. Yu.},
  title     = {On the diameter of the group {$S_N$} with respect to a system of
               generators consisting of a complete cycle and a transposition},
  booktitle = {Trudy po Diskretnoi Matematike},
  volume    = {2},
  publisher = {TVP},
  address   = {Moscow},
  pages     = {112--150},
  year      = {1998},
  url       = {https://www.mathnet.ru/eng/tdm22},
  note      = {In Russian}
}

@article{zubov2010,
  author  = {Zubov, A. Yu.},
  title   = {On the representation of substitutions as products of a
             transposition and a full cycle},
  journal = {Journal of Mathematical Sciences},
  volume  = {166},
  number  = {6},
  pages   = {710--724},
  year    = {2010},
  doi     = {10.1007/s10958-010-9887-z},
  note    = {Russian original: Fundamentalnaya i Prikladnaya Matematika
             \textbf{15}(1) (2009), 31--51}
}

@article{zubov2016,
  author  = {Zubov, A. Yu.},
  title   = {Circular inversions of permutations and their use in sorting problems},
  journal = {Prikladnaya Diskretnaya Matematika},
  number  = {1(31)},
  pages   = {13--31},
  year    = {2016},
  doi     = {10.17223/20710410/31/2},
  url     = {https://www.mathnet.ru/eng/pdm540},
  note    = {In Russian}
}

%======================================================================
% CayleyPy project
%======================================================================

@misc{cayleypygrowth,
  author        = {Chervov, A. and Fedoriaka, D. and Konstantinova, E. and others},
  title         = {{CayleyPy Growth}: Efficient growth computations and hundreds of
                   new conjectures on {Cayley} graphs ({Brief} version)},
  year          = {2025},
  eprint        = {2509.19162},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/2509.19162v2},
  note          = {Version~2, 1~April 2026. Section~4.1, Conjecture~11}
}

@misc{cayleypyrl,
  author        = {Chervov, A. and Soibelman, A. and Lytkin, S. and others},
  title         = {{CayleyPy RL}: Pathfinding and Reinforcement Learning on
                   {Cayley} Graphs},
  year          = {2025},
  eprint        = {2502.18663},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/2502.18663v3},
  note          = {Version~3, 15~May 2026}
}

@misc{CayleyPyHolography2026,
  author        = {Chervov, A. and Levkovich-Maslyuk, F. and Smolensky, A. and others},
  title         = {{CayleyPy-4}: {AI}-Holography. {T}owards analogs of holographic
                   string dualities for {AI} tasks},
  year          = {2026},
  eprint        = {2603.22195},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/2603.22195}
}

%======================================================================
% Babai-type conjecture
%======================================================================

@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}
}

%======================================================================
% Related problems
%======================================================================

@article{kuppilichitturi2020,
  author  = {Kuppili, S. S. and Chitturi, B.},
  title   = {Exact upper bound for sorting {$R_n$} with {LE}},
  journal = {Discrete Mathematics, Algorithms and Applications},
  volume  = {12},
  number  = {3},
  pages   = {2050033},
  year    = {2020},
  doi     = {10.1142/S1793830920500330},
  note    = {12~pp. Author-hosted manuscript:
             \url{https://bpb-us-e2.wpmucdn.com/sites.utdallas.edu/dist/f/1052/files/2023/03/LE.pdf}}
}

@misc{williams2013,
  author        = {Williams, A.},
  title         = {Hamiltonicity of the {Cayley} digraph on the symmetric group
                   generated by {$\sigma=(1\ 2\ \cdots\ n)$} and {$\tau=(1\ 2)$}},
  year          = {2013},
  eprint        = {1307.2549},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/1307.2549v3},
  note          = {Version~3, 6~July 2017}
}

@article{sawadawilliams2020,
  author  = {Sawada, J. and Williams, A.},
  title   = {Solving the {Sigma-Tau} Problem},
  journal = {ACM Transactions on Algorithms},
  volume  = {16},
  number  = {1},
  pages   = {11:1--11:17},
  year    = {2020},
  doi     = {10.1145/3359589},
  note    = {Article~11; published online 15~November 2019}
}

@misc{adinalonroichman2025,
  author        = {Adin, R. M. and Alon, N. and Roichman, Y.},
  title         = {Circular sorting},
  year          = {2025},
  eprint        = {2502.14398},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/2502.14398v2},
  note          = {Version~2, 6~August 2025}
}

@article{diaconisgraham1977,
  author  = {Diaconis, P. and Graham, R. L.},
  title   = {Spearman's footrule as a measure of disarray},
  journal = {Journal of the Royal Statistical Society, Series B},
  volume  = {39},
  number  = {2},
  pages   = {262--268},
  year    = {1977},
  doi     = {10.1111/j.2517-6161.1977.tb01624.x}
}

%======================================================================
% OEIS
%======================================================================

@misc{oeisdiameter,
  author       = {{D.~desJardins and contributors}},
  title        = {{A039745}: Diameter of symmetric group {$S_n$} when generated by
                  {$(1,2)$} and {$(1,2,3,\ldots,n)$}},
  howpublished = {The On-Line Encyclopedia of Integer Sequences},
  url          = {https://oeis.org/A039745},
  note         = {Accessed 29~October 2026}
}

@misc{oeisextremal,
  author       = {{K.~Ryde and contributors}},
  title        = {{A378881}: Irregular triangle listing permutations of
                  {$\{1,\ldots,m\}$} which are at maximum distance from the
                  identity permutation under steps rotate left ({L}) or exchange
                  first two elements ({E})},
  howpublished = {The On-Line Encyclopedia of Integer Sequences},
  year         = {2024},
  url          = {https://oeis.org/A378881},
  note         = {Accessed 29~October 2026}
}

%======================================================================
% Lean / formalisation
%======================================================================

@inproceedings{lean4,
  author    = {de~Moura, L. and Ullrich, S.},
  title     = {The {Lean 4} theorem prover and programming language},
  booktitle = {Automated Deduction -- {CADE} 28},
  series    = {Lecture Notes in Computer Science},
  volume    = {12699},
  publisher = {Springer},
  pages     = {625--635},
  year      = {2021},
  doi       = {10.1007/978-3-030-79876-5_37}
}

@inproceedings{mathlib,
  author    = {{The mathlib Community}},
  title     = {The {Lean} mathematical library},
  booktitle = {Proceedings of the 9th {ACM SIGPLAN} International Conference on
               Certified Programs and Proofs ({CPP} 2020)},
  publisher = {ACM},
  pages     = {367--381},
  year      = {2020},
  doi       = {10.1145/3372885.3373824}
}

@misc{lxformalization,
  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/glushkov-lx-lean/releases/tag/v1.0.0}},
  note         = {Lean 4 formalization, version v1.0.0, commit \texttt{9e04062}},
  year         = {2026},
  month        = nov
}

@unpublished{GuerrieriInPreparation,
  author = {Guerrieri, Andrea},
  note   = {In preparation}
}