Hamiltonicity of expanders: optimal bounds and applications

An n-vertex graph G is a C-expander if |N(X)|≥ C|X| for every X⊆ V(G) with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/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,λ)-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.