PreprintCC BY 4.0arXiv
Hamiltonicity of mildly pseudorandom regular graphs
Abstract
We show that if an (n,d,λ)-graph satisfies λ≤ (1−δ)d and d≫ δ−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.
Related
BibTeX
@misc{muyesser2026hamiltonicity,
title = {{Hamiltonicity of mildly pseudorandom regular graphs}},
author = {Alp Müyesser},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35766},
eprint = {2609.35766},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35766},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hamiltonicity of mildly pseudorandom regular graphs
AU - Alp Müyesser
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35766
UR - https://arxiv.org/abs/2609.35766
AB - We show that if an (n,d,λ)-graph satisfies λ≤ (1−δ)d and d≫ δ^−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.
ER -