Hamiltonicity of regular sublinear expanders

Abstract

We say that a $d$-regular graph is a ${\hat{I}}^3$-expander if for every not too large set of vertices $S$, there are at least ${\hat{I}}^{3}d|S|$ edges leaving $S$, and we say that a graph $G$ is ${\hat{I}}^3$-far from bipartite if at least ${\hat{I}}^{3}e(G)$ edges need to be removed to make it bipartite. We prove that there exists an absolute constant $K$ such that any $n$-vertex $d$-regular ${\hat{I}}^3$-expander with $d \ge (γ^{-1} \log n)^K$ is Hamiltonian, provided that it is bipartite or ${\hat{I}}^3$-far from bipartite. As applications, we obtain highly robust versions of recent important results on the Hamiltonicity of Cayley graphs and Kneser graphs. As part of our proof, we prove a random connecting lemma for sublinear expanders which might be of independent interest.