科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-08-20· math.CO

Small circumference in regular sublinear expanders

Yaobin Chen, Hong Liu, Xin Wei, Fan Yang

原始摘要(英文原文)· Original 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] developed methods yielding nearly Hamilton cycles in sufficiently dense regular sublinear expanders, and Montgomery [ICM 2026] subsequently conjectured that, every sufficiently large (but constant) degree $d$-regular sublinear expander is Hamiltonian. We disprove this conjecture in a strong form by constructing $n$-vertex $d$-regular sublinear expanders with degree $d=\left(\frac12+o(1)\right)\log^2 n$, which does not even has a cycle covering a positive fraction of its vertices. The construction blows up one side of a biregular Ramanujan graph into almost-complete blocks while keeping the other side independent. The Ramanujan incidence graph certifies expansion for arbitrary mixtures of partial blocks and separator vertices, whereas the independent side forms a sparse vertex separator that prevents a cycle from visiting enough blocks. The construction also explains why $\log^2 n$ is the natural degree scale for this obstruction.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

Small circumference in regular sublinear expanders — 科研速览 Science Skim