Pith. sign in

Cutoff on all Ramanujan graphs

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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 + s\sqrt{\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$.

fields

math.PR 1

years

2019 1

verdicts

CONDITIONAL 1

clear filters

representative citing papers

Cutoff for random lifts of weighted graphs

math.PR · 2019-08-08 · conditional · novelty 7.0

Random walks on random n-lifts of any irreducible weighted base graph with two oriented cycles mix at time h^{-1} log n with cutoff, h the universal-cover entropy.

citing papers explorer

Showing 1 of 1 citing paper after filters.

  • Cutoff for random lifts of weighted graphs math.PR · 2019-08-08 · conditional · none · ref 25 · internal anchor

    Random walks on random n-lifts of any irreducible weighted base graph with two oriented cycles mix at time h^{-1} log n with cutoff, h the universal-cover entropy.