Universality of cutoff for graphs with an added random matching

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^{\ast }=(V,E\cup E^{\prime })$ obtained by picking $E^{\prime }$ 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^{\ast }$ exhibits cutoff w.h.p. This provides a simple generic operation of adding some randomness to a given graph, which results in cutoff.

41 pages