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 )