Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The authors prove that any $(n,d,\lambda)$-regular graph is Hamiltonian under the mild spectral gap condition $\lambda \le (1-\delta)d$, pushing the required degree threshold down to $d \gg \delta^{-6}(\log n)^3$. This result significantly tightens and simplifies recent breakthroughs on the minimal pseudorandomness required to guarantee global cycle factors. The bound is achieved by showing that randomly sampled balanced bipartite subgraphs preserve spectral gap properties and admit perfect matchings, which are sequentially woven into a Hamiltonian cycle.
Mild pseudorandomness is sufficient for Hamiltonicity, guaranteeing full cycle covers in regular graphs with only a weak spectral gap and polylogarithmic degree.
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.