首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号