For random Cayley graphs on groups of order N_k, whp diameter ≤ d when p ≥ [(1+ε) d! log N_k / N_k^{d-1}]^{1/d} and diameter > d when p ≤ [(1-ε) 2^{-d} log N_k / N_k^{d-1}]^{1/d} for d up to roughly sqrt(log N / log log N).
The Lov\'asz conjecture holds for moderately dense Cayley graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We show that there is an absolute constant $c>0$ such that every large connected $n$-vertex Cayley graph with degree $d\geq n^{1-c}$ has a Hamilton cycle. This makes progress towards the Lov\'asz conjecture and improves upon the previous best result of this form due to Christofides, Hladk\'y, and M\'ath\'e from 2014 concerning graphs with $d\geq \varepsilon n$. Our proof avoids the use of Szemer\'edi's regularity lemma and relies instead on an efficient arithmetic regularity lemma specialised to Cayley graphs.
fields
math.CO 1years
2026 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Diameter Thresholds of Random Cayley Graphs
For random Cayley graphs on groups of order N_k, whp diameter ≤ d when p ≥ [(1+ε) d! log N_k / N_k^{d-1}]^{1/d} and diameter > d when p ≤ [(1-ε) 2^{-d} log N_k / N_k^{d-1}]^{1/d} for d up to roughly sqrt(log N / log log N).