Almost all vertex-transitive graphs and digraphs are Cayley
We prove that almost all vertex-transitive digraphs are Cayley digraphs, and that almost all vertex-transitive graphs are Cayley graphs, as the number of vertices tends to infinity through all positive integers. The proportions of Cayley objects are at least $1-2^{-n/4+o(n)}$ for digraphs and $1-2^{-n/24+o(n)}$ for graphs. This proves the McKay--Praeger conjecture and its digraph analogue.
Authors
- Binzhou Xia (ORCID: https://orcid.org/0000-0002-8031-2981)
- Ning Su
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.48550/arxiv.2611.23641
- Primary Topic
- Finite Group Theory Research
- Type
- preprint