Amitay Kamber (The Hebrew University)

Thursday, January 2, 2020, 11:10 – 12:00, -101


The cutoff phenomenon of random walks on graphs is conjectured to be very common. However, it is unknown whether many natural examples of large graphs of fixed degree satisfy this phenomenon. It was recently shown by Lubetzky and Peres that Ramanujan graphs, i.e., graphs with the optimal spectrum, exhibit cutoff of the simple random walk in optimal time. We show that the spectral condition can be replaced by a weaker spectral condition, based on the work of Sarnak and Xue in automorphic forms. This property is also equivalent to a geometrical path counting property, which can be verified in some cases. As an example, we show that the theorems hold for some families of Schreier graphs of the $SL_2(F_p)$ action on the projective line, for a finite field $F_p$. Based on joint work with Konstantin Golubev.