Metraipolis › archive › dc_b456db3c8a66

Long-range expanders: construction and cutoff — arXiv:2609.14945

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.14945
License (as archived)
CC0-1.0
Archived
2026-10-16T01:21:12.251Z
SHA-256 of the archived text
e84ae1711863e83ae740c80a2c03b968de1c5df47e8b08f811d97346c2784f95
Stable URL of this page
https://metraipolis.com/documento/dc_b456db3c8a66

How to cite

Long-range expanders: construction and cutoff — arXiv:2609.14945 — arXiv (en), https://arxiv.org/abs/2609.14945 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b456db3c8a66 (Metraipolis archive dc_b456db3c8a66, sha256 e84ae1711863e83ae740c80a2c03b968de1c5df47e8b08f811d97346c2784f95)
BibTeX
@misc{dcb456db3c8a66,
  title = {Long-range expanders: construction and cutoff — arXiv:2609.14945},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.14945},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b456db3c8a66; sha256 e84ae1711863e83ae740c80a2c03b968de1c5df47e8b08f811d97346c2784f95},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14945. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.PR).
Categorie arXiv: Combinatorics (math.CO) ; Metric Geometry (math.MG); Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.14945 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T00:31:28.489Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).