pith. sign in

arxiv: 2605.29457 · v1 · pith:SGXKBKNJnew · submitted 2026-05-28 · 🧮 math.CO

Diameter Thresholds of Random Cayley Graphs

Demetres Christofides , Klas Markstr\"om , Christina Savvidou This is my paper

Pith reviewed 2026-06-29 06:48 UTC · model grok-4.3

classification 🧮 math.CO
keywords Cayley graphsrandom graphsdiameterthresholdsgroup orderErdős-Rényigenerating sets
0
0 comments X

The pith

Random Cayley graphs on groups of order N have diameter at most d with high probability when p is at least the d-th root of d! log N over N^{d-1}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper determines the threshold probabilities p at which random Cayley graphs on a group of order N develop diameter at most d. For any groups with N going to infinity and d up to roughly sqrt(log N over 2 log log N), it gives matching upper and lower bounds on the threshold that differ by constant factors. These bounds are analogous to those in the Erdős-Rényi model but can depend on the group family, and examples show both bounds are tight. Understanding these thresholds reveals when random generating sets produce highly connected Cayley graphs.

Core claim

In the probability space G(G,p) of Cayley graphs where each non-identity element is included in the generating set independently with probability p, for any ε>0 and any family of groups G_k with |G_k|=N_k→∞, and for 2≤d≤d_{N_k} with d_N=(1-γ)sqrt(log N / 2 log log N), a random graph has diameter ≤d whp if p ≥ [(1+ε) d! log N_k / N_k^{d-1}]^{1/d} and diameter >d whp if p ≤ [(1-ε) 2^{-d} log N_k / N_k^{d-1}]^{1/d}.

What carries the argument

The model G(G,p) of random Cayley graphs with independent edge inclusions at probability p, used to derive diameter thresholds via probabilistic analysis of reachability in d steps.

Load-bearing premise

The only property of the groups that matters is their order growing to infinity, with no further dependence on specific relations affecting the diameter in this random model.

What would settle it

Finding a specific family of groups with N large where the diameter threshold for some d falls outside the interval between the two given expressions would disprove the claim.

read the original abstract

Given a group $G$, the model $\mathcal{G}(G,p)$ denotes the probability space of all Cayley graphs of $G$ where each element of $G$ is included in the generating set independently at random with probability $p$. In this article, we investigate the threshold probabilities for the diameter of random graphs in this model. Specifically, let $d_N = (1-\gamma)\sqrt{\frac{\log{N}}{2\log{\log{N}}}}$, where $\gamma \in (0,1)$ is any fixed real number. We show that for any $\varepsilon > 0$, any family of groups $G_k$ of order $N_k$ for which $N_k \to \infty$, and any integer $2 \leqslant d\leqslant d_{N_k}$, a graph $\Gamma_k \in \mathcal{G}(G_k,p)$ with high probability has diameter at most $d$ if $p \geqslant \sqrt[d]{(1+\varepsilon) d! \frac{\log{N_k}}{N_k^{d-1}}}$, and diameter greater than $d$ if $p \leqslant \sqrt[d]{\frac{1-\varepsilon}{2^d} \frac{\log{N_k}}{N_k^{d-1}}}$. Up to a constant factor, these thresholds are similar to those for the usual Erd\H{o}s-R\'enyi random graphs. However, the precise thresholds in our model depend on the underlying family of groups. We provide specific examples of group families demonstrating that both of our bounds are best possible.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper establishes uniform thresholds for the diameter of random Cayley graphs in the model Σ(G,p), where each group element is included independently in the generating set with probability p. For any family of groups G_k with |G_k|=N_k o∞ and any 2≤d≤d_{N_k} with d_N=(1-γ)√(log N/(2 log log N)), a random graph has diameter ≤d whp whenever p ≥ [(1+ε) d! log N_k / N_k^{d-1}]^{1/d} and diameter >d whp whenever p ≤ [(1-ε) 2^{-d} log N_k / N_k^{d-1}]^{1/d}. The paper supplies explicit group families showing that the d! factor in the upper threshold and the 2^{-d} factor in the lower threshold are each asymptotically tight.

Significance. The result supplies a group-independent sandwich on the diameter threshold that holds for every sequence of groups, with the two sides differing by the factor (2^d d!)^{1/d}. The matching examples demonstrate that the constants cannot be improved uniformly. The argument for the diameter >d direction relies only on the elementary ball-size bound |B_≤d(S)| ≤ Σ_{k=0}^d |S|^k together with concentration, while the diameter ≤d direction is asserted to hold uniformly without further group hypotheses beyond |G|=N o∞. These features make the contribution substantial within the study of random Cayley graphs.

minor comments (3)
  1. Abstract: the range d ≤ d_{N_k} is stated with the specific form of d_N involving γ, but the manuscript does not indicate in the abstract why this particular cutoff is required for the stated bounds to hold.
  2. Abstract: the model Σ(G,p) is defined by including each element independently, but it is unclear from the abstract whether the generating set is required to be symmetric (S=S^{-1}) or whether the resulting graphs are directed; this should be clarified in the introduction.
  3. The abstract states that both bounds are best possible but does not name the specific group families used for the matching examples; a brief indication of the constructions (e.g., elementary abelian 2-groups or free groups) would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our results on diameter thresholds in random Cayley graphs, as well as the recommendation for minor revision. No specific major comments or criticisms were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives explicit diameter thresholds for the random Cayley graph model G(G,p) via probabilistic arguments. The lower bound on the threshold follows from the group-independent combinatorial estimate |B_{\leq d}(S)| \le \sum_{k=0}^d |S|^k together with binomial concentration on |S|; the upper bound is asserted to hold uniformly over all group families of order N_k \to \infty by a separate probabilistic construction whose details are independent of any fitted quantities or prior self-citations. The paper explicitly notes that the precise constant inside the gap depends on the group family and supplies matching examples, confirming that the stated sandwich is not tautological. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citation chains appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; the model definition itself is the only structural assumption visible.

pith-pipeline@v0.9.1-grok · 5822 in / 1186 out tokens · 37444 ms · 2026-06-29T06:48:01.450618+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 3 canonical work pages · 1 internal anchor

  1. [1]

    Alon and J

    N. Alon and J. H. Spencer,The probabilistic method, fourth edition, Wiley, 2016

    2016

  2. [2]

    Babai and A

    L. Babai and A. Seress, On the diameter of permutation groups, European Journal of Combinatorics, 13(1992), 231–243

    1992

  3. [3]

    The Lov\'asz conjecture holds for moderately dense Cayley graphs

    B. Bedert, N. Dragani´ c, A. M¨ uyesser and M. Pavez-Sign´ e, The Lov´ asz conjecture holds for moderately dense Cayley graphs,arXiv:2603.08675

    work page internal anchor Pith review Pith/arXiv arXiv

  4. [4]

    Behague, D

    N. Behague, D. Il’koviˇ c and R. Montgomery, A proof of the Kim-Vu sandwich conjecture, arXiv:2510.20765

    work page arXiv

  5. [5]

    Bollob´ as,Random graphs, Second edition, Cambridge Univ

    B. Bollob´ as,Random graphs, Second edition, Cambridge Univ. Press, 2001

    2001

  6. [6]

    Breuillard, B

    E. Breuillard, B. Green and T. Tao, Approximate subgroups of linear groups, Geometric and Func- tional Analysis,21(2011), 774–819

    2011

  7. [7]

    Christofides, J

    D. Christofides, J. Hladk´ y and A. M´ ath´ e, Hamilton cycles in dense vertex-transitive graphs, Journal of Combinatorial Theory, Series B,109(2014), 34–72

    2014

  8. [8]

    Christofides and K

    D. Christofides and K. Markstr¨ om, Expansion properties of random Cayley graphs and vertex tran- sitive graphs via matrix martingales, Random Structures Algorithms,32(2008), 88–100

    2008

  9. [9]

    Christofides and K

    D. Christofides and K. Markstr¨ om, Random Latin square graphs, Random Structures & Algorithms, 21(2012), 47–65

    2012

  10. [10]

    Christofides and K

    D. Christofides and K. Markstr¨ om, The thresholds for diameter 2 in random Cayley graphs, Random Structures & Algorithms,45(2014), 218–235

    2014

  11. [11]

    Eberhard and U

    S. Eberhard and U. Jezernik, Babai’s conjecture for high-rank classical groups with random gener- ators, Inventiones Mathematicae,227(2022), 149–210

    2022

  12. [12]

    El-Baz and C

    D. El-Baz and C. Pagano, Diameters of random Cayley graphs of finite nilpotent groups, Journal of Group Theory,24(2021), 1043–1053

    2021

  13. [13]

    Garonzi, Z

    M. Garonzi, Z. Halasi and G. Somlai, On the diameter of Cayley graphs of classical groups with generating sets containing a transvection, Israel Journal of Mathematics,261(2024), 899–950

    2024

  14. [14]

    P. Gao, M. Isaev and B. D. McKay, Kim–Vu’s sandwich conjecture is true ford≫log 4 n, arXiv:2011.09449

    work page arXiv 2011

  15. [15]

    Glock, D

    S. Glock, D. Munh´ a Correia and B. Sudakov, Hamilton cycles in pseudorandom graphs, Advances in Mathematics,458(2024), 109984

    2024

  16. [16]

    Halasi, Diameter of Cayley graphs ofSL(n, p) with generating sets containing a transvection, Journal of Algebra,569(2021), 195–219

    Z. Halasi, Diameter of Cayley graphs ofSL(n, p) with generating sets containing a transvection, Journal of Algebra,569(2021), 195–219

    2021

  17. [17]

    H. A. Helfgott and A. Seress, On the diameter of permutation groups, Annals of Mathematics,179 (2014), 611–658

    2014

  18. [18]

    Hermon and S

    J. Hermon and S. Olesker-Taylor, Geometry of random Cayley graphs of Abelian groups, Annals of Applied Probability,33(2023), 3520–3562

    2023

  19. [19]

    J. H. Kim, B. Sudakov and V. H. Vu, On the asymmetry of random regular graphs and random graphs, Random Structures & Algorithms21(2002), 216–224

    2002

  20. [20]

    J. H. Kim and V. H. Vu, Sandwiching random graphs: universality between random graph models, Adv. Math.188(2004), 444–469

    2004

  21. [21]

    Krivelevich and B

    M. Krivelevich and B. Sudakov, Sparse pseudo-random graphs are Hamiltonian, Journal of Graph Theory,42(2003), 17–33

    2003

  22. [22]

    Marklof, The asymptotic distribution of Frobenius numbers, Inventiones Mathematicae,181 (2010), 179–207

    J. Marklof, The asymptotic distribution of Frobenius numbers, Inventiones Mathematicae,181 (2010), 179–207

    2010

  23. [23]

    Marklof and A

    J. Marklof and A. Str¨ ombergsson, Diameters of random circulant graphs, Combinatorica,33(2013), 429–466

    2013

  24. [24]

    Pham and X

    L. Pham and X. Zhang, Logarithmic diameter bounds for some Cayley graphs, Journal of Group Theory,25(2022), 327–342

    2022

  25. [25]

    N. T. Sardari, Diameter of Ramanujan graphs and random Cayley graphs, Combinatorica,39(2019), 427–446

    2019