Return to Colloquia & Seminar listing
Bounded window cutoff for random walks on Ramanujan graphs
ProbabilitySpeaker: | Evita Nestoridi, Princeton University |
Location: | zoom |
Start time: | Wed, May 19 2021, 4:10PM |
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.