Hamiltonicity of mildly pseudorandom regular graphs

Source abstract

We show that if an $(n,d,λ)$-graph satisfies $λ\leq (1-δ)d$ and $d\gg δ^{-6}(\log n)^{3}$ for some $δ>0$, then it is Hamiltonian. A qualitatively similar result was recently proven by Bradač and Janzer. Our proof here is shorter and gives better quantitative bounds. \par In our proof, as in earlier work of Ferber, Han, Mao, and Vershynin, we use a random matrix inequality to show that a mild spectral gap is typically preserved after randomly sampling an appropriate proportion of the vertices. This allows us to deduce that typical balanced bipartite subgraphs of pseudorandom graphs contain perfect matchings. To convert a collection of perfect matchings into a Hamilton cycle, we use a variant of the sorting network method.