Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

In 2016, Lubetzky and Peres proved that on every Ramanujan graph $G$ with $n$ vertices and degree $d$, the simple random walk exhibits cutoff at $d(d-2)^{-1} \log_{d-1} n$. In this talk, we will focus on the non-backtracking random walk on $G$ and prove that it exhibits cutoff at $\log_{d-1} n$ with a bounded window, provided that the girth of $G$ is big. This is joint work with Peter Sarnak.