Hamiltonicity of sparse pseudorandom graphs
Asaf Ferber, Jie Han, Dingjia Mao, Roman Vershynin · Combinatorics Probability Computing · 2025
Abstract We show that every $(n,d,\lambda )$ -graph contains a Hamilton cycle for sufficiently large $n$ , assuming that $d\geq \log ^{6}n$ and $\lambda \leq cd$ , where $c=\frac {1}{70000}$ . This significantly improves a recent result of Glock, Correia, and Sudakov, who obtained a similar result for $d$ that grows polynomially with $n$ . The proof is based on a new result regarding the second largest eigenvalue of the adjacency matrix of a subgraph induced by a random subset of vertices, combined with a recent result on connecting designated pairs of vertices by vertex-disjoint paths in $(n,d,\lambda )$ -graphs. We believe that the former result is of independent interest and will have further applications.