![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
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 )