Cutoff for random Cayley graphs of finite groups

Abstract

We study the random walk on a Cayley graph of a finite group whose generators are chosen independently and uniformly at random. We show that, for every finite group, the walk exhibits cutoff with high probability whenever the number of generators is at least a constant multiple of the logarithm of the order of the group and small compared with every positive power of it. This holds for both undirected and directed Cayley graphs, in discrete and continuous time, and the lower bound on the number of generators is best possible, up to the value of the constant. The cutoff time is the time at which the expected entropy of the walk comes close to its maximum, and in general it depends on the structure of the group. This settles a conjecture of Aldous and Diaconis.

Exact Diameter Windows for Random Cayley Graphs on Odd-Order Abelian Groups
Yao Zhi
arXiv1 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv
D^L, D^Q Spectrum and Eigenvalue-free Interval of Cayley Graphs over Finite Nilpotent Groups
Pallabi Manna, Santanu Mandal
arXiv9 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Heat kernels on Cayley graphs of free products of finite groups
Kamila Kashaeva
arXiv23 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Analysis & PDEsarXiv
Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
Kengo Enami, Takahiro Matsushita
arXiv26 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Coloring sparse random Cayley graphs
Nathan Tung
arXiv12 Aug 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematics ProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhu2026cutoff,
  title = {{Cutoff for random Cayley graphs of finite groups}},
  author = {Haoran Zhu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41347},
  eprint = {2610.41347},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41347},
}

RIS

TY  - UNPB
TI  - Cutoff for random Cayley graphs of finite groups
AU  - Haoran Zhu
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41347
UR  - https://arxiv.org/abs/2610.41347
AB  - We study the random walk on a Cayley graph of a finite group whose generators are chosen independently and uniformly at random. We show that, for every finite group, the walk exhibits cutoff with high probability whenever the number of generators is at least a constant multiple of the logarithm of the order of the group and small compared with every positive power of it. This holds for both undirected and directed Cayley graphs, in discrete and continuous time, and the lower bound on the number of generators is best possible, up to the value of the constant. The cutoff time is the time at which the expected entropy of the walk comes close to its maximum, and in general it depends on the structure of the group. This settles a conjecture of Aldous and Diaconis.
ER  -

Abstract

Related

Cite