There exists K such that any n-vertex d-regular γ-expander with d ≥ (γ^{-1} log n)^K is Hamiltonian if bipartite or γ-far from bipartite.
The Lov\'asz conjecture holds for moderately dense Cayley graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers 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 2years
2026 2verdicts
UNVERDICTED 2representative citing papers
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).
citing papers explorer
-
Hamiltonicity of regular sublinear expanders
There exists K such that any n-vertex d-regular γ-expander with d ≥ (γ^{-1} log n)^K is Hamiltonian if bipartite or γ-far from bipartite.
-
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).