Cutoff for Ramanujan graphs via degree inflation

19 Mar 2018

Recently Lubetzky and Peres showed that simple random walks on a sequence of d-regular Ramanujan graphs Gn = (Vn, En) of increasing sizes exhibit cutoff in total variation around the diameter lower bound d d−2 logd−1 |Vn|. We provide a different argument under the assumption that for some r(n) 1 the maximal number of simple cycles in a ball of radius r(n) in Gn is uniformly bounded in n.