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 G*n exhibits cutoff w.h.p.
All Science Journal Classification (ASJC) codes
- Statistics and Probability
- Statistics, Probability and Uncertainty
- Mixing time
- Quasi trees
- Random graph