Nonhamiltonian regular sublinear expanders

Abstract

Letzter, Methuku and Sudakov proved that sufficiently regular sublinear expanders contain nearly spanning cycles and paths. Montgomery subsequently conjectured that every regular sublinear expander of sufficiently large degree is hamiltonian. Recently, Chen, Liu, Wei and Yang disproved this conjecture by constructing $d$-regular sublinear expanders of order $n$ with $d=(1/2+o(1)){\log }^{2}n$ and small circumference. They further posed the problem of determining whether, for every fixed $\epsilon >0$, there exists a constant $C=C(\epsilon )$ such that every sufficiently large $n$-vertex $d$-regular $(\epsilon ,d)$-expander with $d\ge C{\log }^{2}n$ is hamiltonian. We answer this problem negatively by constructing, for every sufficiently small fixed $\epsilon >0$, infinitely many nonhamiltonian $d$-regular $(\epsilon ,d)$-expanders with degrees far above the ${\log }^{2}n$ scale.

7 pages