Talks

Spring 2016

# Cutoff on all Ramanujan Graphs

Monday, Feb. 22, 2016 2:55 pm – 3:40 pm

Location:

Calvin Lab

Abstract: Lubotzky, Phillips, and Sarnak (1988) defined a connected $d$-regular graph $G$ (with $d>2$) to be Ramanujan iff for every eigenvalue of its adjacency matrix, its absolute value is either $d$, or at most $2(d-1)^{1/2}$. We show that on every Ramanujan graph $G$ with $n$ vertices, simple random walk exhibits cutoff: the mixing time in total-variation is asymptotic to $[d/(d-2)] \log_{d-1} n$. Furthermore, for any $p$ which is at least 1, the $d$-regular Ramanujan graphs minimize the asymptotic $L^p$-mixing time among all $d$-regular graphs. In particular, this gives the first examples of transitive expanders with cutoff. Our proof also shows that, for every vertex in an $n$-vertex Ramanujan graph $G$, its distance from all but a negligible fraction of the other vertices in $G$ is asymptotically $\log_{d-1} n$.

The key to our proofs is a precise spectral analysis of the non-backtracking walk. (Joint work with Eyal Lubetzky, NYU http://arxiv.org/abs/1507.04725 )

Attachment | Size |
---|---|

Cutoff on all Ramanujan Graphs | 4.19 MB |