Universality of cutoff for graphs with an added random matching

2020/08/19 by Hermon, Jonathan, Sly, Allan, Sousi, Perla
#05C81 #FOS: Mathematics #Primary: 60J10 #Probability (math.PR) #Secondary: 05C80

paper · doi:10.48550/arxiv.2008.08564

Abstract

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 G_n of diverging sizes and of uniformly bounded degree, if the minimal size of a connected component of G_n is at least 3 for all n, then the random walk on G_n^* exhibits cutoff w.h.p. This provides a simple generic operation of adding some randomness to a given graph, which results in cutoff.

Related

• Cutoff for random walk on random graphs with a community structure
• Phase transition for random walks on graphs with added weighted random matching
• Cutoff for random lifts of weighted graphs
• Cutoff for non-backtracking random walks on sparse random graphs
• Cutoff Phenomenon for Random Walks on Kneser Graphs