Abstract
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 )