Yuval Peres: An introduction to Ramanujan graphs and random walks on them, January 25, 2016

Abstract:
Lubotzky, Phillips, and Sarnak (1988) defined a connected $d$-regular graph $G$ (with $d$ at least 3) to be Ramanujan if and only if 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.

More Information:
▪ Related Presentation: An Introduction to Ramanujan Graphs and Random Walks on Them
▪ Related publication: Lubetzky, Eyal, and Yuval Peres. "Cutoff on all Ramanujan graphs." Geometric and Functional Analysis 26, no. 4 (2016): 1190-1216.