paper

Cutoff for random lifts of weighted graphs

arXiv:1908.02898

Abstract

We prove a cutoff for the random walk on random -lifts of finite weighted graphs, even when the random walk on the base graph of the lift is not reversible. The mixing time is w.h.p. , where is a constant associated to , namely the entropy of its universal cover. Moreover, this mixing time is the smallest possible among all -lifts of . In the particular case where the base graph is a vertex with loops, even, we obtain a cutoff for a -regular random graph (as did Lubetzky and Sly in \cite{cutoffregular} with a slightly different distribution on -regular graphs, but the mixing time is the same).

arXiv comment38 pages, 2 figures