Abstract:
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 proof 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. The proof exploits a quantitative relation between hitting-times and mixing times.
Biography:
Jonathan Hermon is currently a Postdoc at the Stats Lab at Cambridge. Before that he was a Postdoc at the Weizmann Institute of Science. He got his Ph.D. from UC Berkeley, where he was mentored by Allan Sly. His research interests include Markov chains (mixing, cutoff and general theory), random walks, random graphs, particle systems and random graphs.
Seminar by the NYU-ECNU Institute of Mathematical Sciences at NYU Shanghai