Long-range expanders: construction and cutoff

Abstract

Long-range expansion is a combinatorial graph property introduced to construct metric spaces with strong quantitative obstructions to low-distortion embeddings. Such extremal constructions are motivated by fundamental questions in metric geometry and nonlinear functional analysis. However, the only known constructions of long-range expander sequences are random regular graphs; the problem of constructing explicit sequences, especially with logarithmic girth, remains open. We resolve this question in strong form by proving that the Ramanujan condition implies long-range expansion. In particular, classical Ramanujan constructions (such as LPS graphs) give explicit long-range expander sequences with logarithmic girth. We also clarify that long-range expansion implies spectral expansion, and both implications are strict. While long-range expansion, the Ramanujan property, and spectral expansion are strictly separated, it is \textit{a priori} not clear how robust these gaps are. We next compare them from a dynamics perspective: how do the different notions of expansion affect the mixing rate of random walks? Our second main result is that, from a dynamics perspective, LRE and the Ramanujan property are equivalent. We show that the random walk on any LRE sequence has the same cutoff location and Gaussian limit profile as on a Ramanujan graph. This incidentally offers intermediate progress between cutoff for Ramanujan graphs---proven by Lubetzky and Peres---and the long-standing conjecture of cutoff for transitive spectral expanders.

Arithmetic localization for quasiperiodic long-range operators with monotone potentials
Hongyi Cao
arXiv29 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Dynamical systemsarXiv
Arithmetic k-Polynomial Dynamical Localization for k Power-Law Quasi-Periodic Long-Range Operators on ℓ²(ℤ^d)
Ao Cai, Huihui Lv, Yuan Shan +1
arXiv22 Sep 2026PreprintarXiv licenceFull textDynamical systemsarXiv
Finite- and long-range spin-wave free-energy asymptotics for the two-dimensional quantum Heisenberg ferromagnet
Andreas Klippel
arXiv7 Oct 2026PreprintCC BY 4.0Full textMathematical physics ProbabilityarXiv
Continuity of the phase transition for long-range Bernoulli percolation with exponential decay on ℤ²
Omer Angel, Daniel de la Riva, Christoforos Panagiotis +1
arXiv26 Oct 2026PreprintarXiv licenceFull textProbabilityarXiv
Mixing time and isoperimetry of long-range percolation in the diffusive regime
Dieter Mitsche, Carlo Scali
arXiv8 Oct 2026PreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{altschuler2026longrange,
  title = {{Long-range expanders: construction and cutoff}},
  author = {Dylan J. Altschuler},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.14945},
  eprint = {2609.14945},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.14945},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Long-range expanders: construction and cutoff
AU  - Dylan J. Altschuler
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2609.14945
UR  - https://arxiv.org/abs/2609.14945
AB  - Long-range expansion is a combinatorial graph property introduced to construct metric spaces with strong quantitative obstructions to low-distortion embeddings. Such extremal constructions are motivated by fundamental questions in metric geometry and nonlinear functional analysis. However, the only known constructions of long-range expander sequences are random regular graphs; the problem of constructing explicit sequences, especially with logarithmic girth, remains open. We resolve this question in strong form by proving that the Ramanujan condition implies long-range expansion. In particular, classical Ramanujan constructions (such as LPS graphs) give explicit long-range expander sequences with logarithmic girth. We also clarify that long-range expansion implies spectral expansion, and both implications are strict. While long-range expansion, the Ramanujan property, and spectral expansion are strictly separated, it is \textit{a priori} not clear how robust these gaps are. We next compare them from a dynamics perspective: how do the different notions of expansion affect the mixing rate of random walks? Our second main result is that, from a dynamics perspective, LRE and the Ramanujan property are equivalent. We show that the random walk on any LRE sequence has the same cutoff location and Gaussian limit profile as on a Ramanujan graph. This incidentally offers intermediate progress between cutoff for Ramanujan graphs---proven by Lubetzky and Peres---and the long-standing conjecture of cutoff for transitive spectral expanders.
ER  -

Abstract

Related

Cite