Cutoff for Ramanujan graphs via degree inflation
Cutoff for Ramanujan graphs via degree inflation
复制标题
通过度数膨胀对拉马努金图进行截止
DOI：
10.1214/17-ecp72
复制
发表时间：
2017
影响因子：
0.5
通讯作者：
J. Hermon
中科院分区：
文献类型：
--
作者：
J. Hermon
最近，Lubetzky和Peres证明了在一个长度递增的d$-正则Ramanujan图序列G_n=（V_n，E_n）$上的简单随机游动在直径下界$\frac{d}{d-2}\log_{d-1}附近的全变差截断|V_n| $.我们提供了一个不同的论点的假设下，对一些$r（n）\gg 1$的最大数量的简单循环在一个球的半径$r（n）$在$G_n$是一致有界的$n$。
Recently Lubetzky and Peres showed that simple random walks on a sequence of $d$-regular Ramanujan graphs $G_n=(V_n,E_n)$ of increasing sizes exhibit cutoff in total variation around the diameter lower bound $\frac{d}{d-2}\log_{d-1}|V_n| $. We provide a different argument under the assumption that for some $r(n) \gg 1$ the maximal number of simple cycles in a ball of radius $r(n)$ in $G_n$ is uniformly bounded in $n$.