Small circumference in regular sublinear expanders
Abstract
Sublinear expansion is weak enough to be extracted from arbitrary graphs while retaining nearly all of their average degree, yet it has proved strong enough to force global structures in many sparse extremal problems. Letzter, Methuku and Sudakov [JLMS 2026] proved the existence of nearly Hamilton cycles in sufficiently dense regular sublinear expanders. Montgomery [ICM 2026] subsequently conjectured that, every d-regular sublinear expander with d sufficiently large (but constant) is Hamiltonian. We disprove this conjecture in a strong form by constructing n-vertex d-regular sublinear expanders with d=(1/2+o(1))log2 n, which can forbid any cycle covering an arbitrarily small given positive constant portion of its vertices. The construction blows up one side of a biregular Ramanujan graph into almost-complete blocks and keeps the other side as a sparse vertex separator. We also prove a similar statement for a closely related notion of edge expanders. For every sufficiently small γ>0, there is an infinite family of n-vertex d-regular γ-edge-expanders with d=Θ(γ−1) and circumference O(γn), matching the standard lower bound Ω(γn). The construction also comes from an expanding regular core such that each vertex has an almost-complete graph attached to it. The core guarantees edge expansion, while the single-vertex attachments confine every cycle.
Related
- Repeated averaging on expanders I: random d-regular graph
- Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs
- Enumeration of small vertex-transitive directed strongly regular graphs
- Logical isomorphism and logical limit laws for small permutation classes and regular languages
- On knotted self expanders of the mean curvature flow in R3
BibTeX
@misc{chen2026small,
title = {{Small circumference in regular sublinear expanders}},
author = {Yaobin Chen and Hong Liu and Xin Wei and Fan Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.20190},
eprint = {2608.20190},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.20190},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Small circumference in regular sublinear expanders
AU - Yaobin Chen
AU - Hong Liu
AU - Xin Wei
AU - Fan Yang
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2608.20190
UR - https://arxiv.org/abs/2608.20190
AB - Sublinear expansion is weak enough to be extracted from arbitrary graphs while retaining nearly all of their average degree, yet it has proved strong enough to force global structures in many sparse extremal problems. Letzter, Methuku and Sudakov [JLMS 2026] proved the existence of nearly Hamilton cycles in sufficiently dense regular sublinear expanders. Montgomery [ICM 2026] subsequently conjectured that, every d-regular sublinear expander with d sufficiently large (but constant) is Hamiltonian. We disprove this conjecture in a strong form by constructing n-vertex d-regular sublinear expanders with d=(1/2+o(1))log^2 n, which can forbid any cycle covering an arbitrarily small given positive constant portion of its vertices. The construction blows up one side of a biregular Ramanujan graph into almost-complete blocks and keeps the other side as a sparse vertex separator. We also prove a similar statement for a closely related notion of edge expanders. For every sufficiently small γ>0, there is an infinite family of n-vertex d-regular γ-edge-expanders with d=Θ(γ^−1) and circumference O(γn), matching the standard lower bound Ω(γn). The construction also comes from an expanding regular core such that each vertex has an almost-complete graph attached to it. The core guarantees edge expansion, while the single-vertex attachments confine every cycle.
ER -