Cutoff for Ramanujan graphs via degree inflation.

Cutoff for Ramanujan graphs via degree inflation.

-
Jonathan Hermon, Cambridge University
Fine Hall 110

Recently Lubetzky and Peres showed that simple random walks on a sequence of d-regular Ramanujan graphs G_n=(V_n,E_n) of increasing sizes exhibit cutoff in total variation around the diameter lower bound \frac{d}{d-2}\log_{d-1}|V_n|. We provide a different proof under the assumption that for some r(n) \gg 1 the maximal number of simple cycles in a ball of radius r(n) in G_n is uniformly bounded in n.