Cutoff on all Ramanujan graphs

By Eyal Lubetzky, Yuval Peres. 2015

87 citations recorded by the source corpus.

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

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/fcc10025269edde5c4458baef5614e1a71f10dbb

Citations in the corpus