Hamiltonicity of expanders: optimal bounds and applications

An $n$-vertex graph $G$ is a $C$-expander if $\mathrm{\mid }N(X)\mathrm{\mid }\ge C\mathrm{\mid }X\mathrm{\mid }$ for every $X\subseteq V(G)$ with $\mathrm{\mid }X\mathrm{\mid }<n\mathrm{/}2C$ and there is an edge between every two disjoint sets of at least $n\mathrm{/}2C$ vertices. We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda )$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications, including to the Hamiltonicity of random Cayley graphs.