Cutoff on all Ramanujan graphs |
| |
Authors: | Eyal Lubetzky Yuval Peres |
| |
Affiliation: | 1.Courant Institute,New York University,New York,USA;2.Microsoft Research,Redmond,USA |
| |
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=frac{d}{d-2} log_{d-1} n + ssqrt{log n}}) is asymptotically ({{mathbb{P}}(Z > c , s)}) where ({Z}) is a standard normal variable and ({c=c(d)}) is an explicit constant. Furthermore, for all ({1 leq p leq infty}), ({d})-regular Ramanujan graphs minimize the asymptotic ({L^p})-mixing time for SRW among all ({d})-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-1} n}). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|