Cutoff for Random Walks on Random Graphs at the Entropic Time

(Joint work with Perla Sousi.)

A sequence of Markov chains is said to exhibit cutoff if it exhibits an abrupt convergence to equilibrium. Loosely speaking, this means that the epsilon mixing time (i.e. the first time the worst-case total-variation distance from equilibrium is at most epsilon) is asymptotically independent of epsilon. An emerging paradigm is that cutoff is related to entropic concentration. In the case of random walks on random graphs G=(V,E), the entropic time can be defined as the time at which the entropy of random walk on some auxiliary graph (often the Benjamini-Schramm limit) is log |V|. Previous works established cutoff at the entropic time in the case of the configuration model. We consider a random graph model in which a random graph G'=(V,E') is obtained from a given graph G=(V,E) with an even number of vertices by picking a random perfect matching of the vertices, and adding an edge between each pair of matched vertices. We prove cutoff at the entropic time, provided G is of bounded degree and its connected components are of size at least 3. Previous works were restricted to the case that the random graph is locally tree-like.