Metraipolis › archive › dc_1920caab376c

Repeated averaging on expanders I: random $d$-regular graph — arXiv:2609.25729

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.25729
License (as archived): CC0-1.0
Archived: 2026-10-08T15:54:23.699Z
SHA-256 of the archived text: 1ceee40cae5051efaa069e870099b18108e7e81501036c1d3f26bf757335edc3
Stable URL of this page: https://metraipolis.com/documento/dc_1920caab376c

How to cite

Repeated averaging on expanders I: random $d$-regular graph — arXiv:2609.25729 — arXiv (en), https://arxiv.org/abs/2609.25729 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1920caab376c (Metraipolis archive dc_1920caab376c, sha256 1ceee40cae5051efaa069e870099b18108e7e81501036c1d3f26bf757335edc3)

BibTeX

@misc{dc1920caab376c,
  title = {Repeated averaging on expanders I: random $d$-regular graph — arXiv:2609.25729},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.25729},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1920caab376c; sha256 1ceee40cae5051efaa069e870099b18108e7e81501036c1d3f26bf757335edc3},
  year = {2026}
}

Archived text

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

Repeated averaging on graphs is a natural prototype of local stochastic exchange, modeling consensus formation, information spreading, and wealth redistribution. Its convergence has attracted longstanding interest, from Bourgain's complete-graph $L^1$ cutoff question in the 80s (answered in recent years by Chatterjee, Diaconis, Sly, and Zhang) and the systematic study of Aldous and Lanoue. Addressing the still outstanding and widely asked $L^1$-cutoff question on general graphs, we establish a criterion based on size-biased sampling, and develop a general framework for sparse expanders. Specifically, we prove $L^1$ cutoff with a Gaussian profile on random $d$-regular graphs, for any $d\ge 3$ and uniformly over starting vertices. Remarkably, although the expected mass profile agrees exactly with the corresponding random-walk distribution, cutoff occurs strictly later than both the random walk cutoff time and the universal lower bound attained on complete graphs, revealing an unexpected entropy gap. The framework is robust, involving ideas of polymer representations, random geometry, universal-cover lifting, and adaptive revealing. Our companion work will extend it to Ramanujan graphs and bounded-degree configuration models.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-23 in math.PR).
Categorie arXiv: Probability (math.PR).
Pagina del lavoro: https://arxiv.org/abs/2609.25729 — 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-08T15:13:13.517Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).