Cutoff on all Ramanujan graphs

Eyal Lubetzky, Yuval Peres

Research output: Contribution to journalArticlepeer-review

Abstract

We show that on every Ramanujan graph G, the simple random walk exhibits cutoff: when G has n vertices and degree d, the total-variation distance of the walk from the uniform distribution at time t=dd-2logd-1n+slogn is asymptotically P(Z>cs) where Z is a standard normal variable and c= c(d) is an explicit constant. Furthermore, for all 1 ≤ p≤ ∞, d-regular Ramanujan graphs minimize the asymptotic Lp-mixing time for SRW among alld-regular graphs. Our proof also shows that, for every vertex x in G as above, its distance from n- o(n) of the vertices is asymptotically log d-1n.

Original languageEnglish (US)
Pages (from-to)1190-1216
Number of pages27
JournalGeometric and Functional Analysis
Volume26
Issue number4
DOIs
StatePublished - Jul 1 2016

ASJC Scopus subject areas

  • Analysis
  • Geometry and Topology

Fingerprint Dive into the research topics of 'Cutoff on all Ramanujan graphs'. Together they form a unique fingerprint.

Cite this