Universality of cutoff for graphs with an added random matching
Jonathan Hermon, Allan Sly, Perla Sousi · The Annals of Probability · 2022
We establish universality of cutoff for simple random walk on a class of random graphs defined as follows. Given a finite graph G=(V,E) with |V| even we define a random graph G∗=(V,E∪E′) obtained by picking E′ to be the (unordered) pairs of a random perfect matching of V. We show that for a sequence of such graphs Gn of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of Gn is at least 3 for all n, then the random walk on Gn∗ exhibits cutoff w.h.p. This provides a simple generic operation of adding some randomness to a given graph, which results in cutoff.