Cutoff for random lifts of weighted graphs (Q2119212)

The way random walks converge to equilibrium on a graph is closely related to essential geometrical properties of the latter (such as the typical distance between vertices, its diameter, its expansion, the presence of traps or bottlenecks, etc.), giving an important motivation for studying mixing times. A class of graphs where random walks mix fast and where cutoff is expected are the expander graphs. A natural way of combining the ``product of a base space'' and the ``expanding sparse graph'' perspectives for cutoff is to consider random walks on random \(n\)-lifts of a fixed graph \(G\). Here, the author establishes the cutoff phenomenon for the random walk on random \(n\)-lifts of finite weighted graphs, even when the random walk on the base graph \(G\) of the lift is not reversible. The mixing time is w.h.p. \(t_{\mathrm{mix}} = h^{-1}\log n \), where \(h\) is a constant associated to \(G\), namely the entropy of its universal cover. Moreover, this mixing time is the smallest possible among all \(n\)-lifts of \(G\). In the particular case where the base graph is a vertex with \( d/2\) loops, \(d\) even, the author finds a cutoff for a \(d\)-regular random graph, as did \textit{E. Lubetzky} and \textit{A. Sly} [Duke Math. J. 153, No. 3, 475--510 (2010; Zbl 1202.60012)] (with a slightly different distribution on \(d\)-regular graphs, but the mixing time is the same). The paper contains useful materials of interdisciplinary nature. Special focus on researchers working on random walks.