Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 31 min ago
PreprintCC BY 4.0arXiv

Cayley graph diameters for fixed cycle types are eventually quasipolynomial

  • Andrei Smolensky
Open at sourcePDFDOICite

Abstract

Given a cycle type, the corresponding conjugacy class of Sn generates either Sn or An for sufficiently large n. We prove that the sequence of diameters of Cayley graphs is eventually polynomial on residue classes for any fixed cycle type. This result is also extended to finite unions of conjugacy classes.

Related

  1. Every graph is eventually Turán-good and Turán-stable
    Jiabao Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A non-plain virtually free group with a strictly 2-geodetic Cayley graph
    André Carvalho
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  3. Cayley-graph density of Thompson's group F: local deletions and finite-window bounds
    Thomas Prellberg
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. The Cayley Completion of a Graph
    Rigobert Fokam Souop, Laurent Bitjoka
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A Quasipolynomial Algorithm for ℓ∞ Contractions
    Ashkan Soleymani, Gabriele Farina
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{smolensky2026cayley,
  title = {{Cayley graph diameters for fixed cycle types are eventually quasipolynomial}},
  author = {Andrei Smolensky},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.08385},
  eprint = {2610.08385},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.08385},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Cayley graph diameters for fixed cycle types are eventually quasipolynomial
AU  - Andrei Smolensky
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2610.08385
UR  - https://arxiv.org/abs/2610.08385
AB  - Given a cycle type, the corresponding conjugacy class of S_n generates either S_n or A_n for sufficiently large n. We prove that the sequence of diameters of Cayley graphs is eventually polynomial on residue classes for any fixed cycle type. This result is also extended to finite unions of conjugacy classes.
ER  -