Universality of cutoff for graphs with an added random matching (Q2119210)

The question of when a family of graphs exhibits the cutoff phenomenon for a simple random walk on it (crudely, that the random walk goes suddenly from being obviously far from its long-term stationary distribution to being very close to it) is of importance. \textit{P. Diaconis} [Bernoulli 19, No. 4, 1294--1305 (2013; Zbl 1412.60109)] poses the question of considering the cutoff phenomenon when a regular connected graph (on an even number of vertices) is taken and a perfect matching is added to it. The main result of the paper under review is somewhat more general than Diaconis's question. If \(G_{n}=(V_{n},E_{n})\) is a sequence of graphs of even orders, with the orders diverging to infinity, with maximum degree at most a constant \(\Delta\in \mathbb{N}\) and with all components of order at least 3, then the cutoff phenomenon holds for simple random walk on the graphs \(G_{n}^{\ast}\) when a random perfect matching is added to \(G_{n}\) whp -- i.e. with probability tending to 1 as the number of vertices tends to infinity. More precisely, we formally measure distance from the stationary distribution \(\pi\) by the \(\epsilon\)-total variation mixing time \(t_{\text{mix}}(G, \epsilon)=\min\{t\geq 0: \max_{x} \| P^{t}(x,\cdot)-\pi \|_{TV} <\epsilon\}\) where \(P\) is the one-step transition matrix and as usual \(\| \cdot \|_{TV}\) is the total variation distance; informally this is the time at which, even in the worst case over all potential starting points, the distance at time \(t\) from the stationary distribution is less than \(\epsilon\). Then the authors show that for \(\epsilon \in (0,1/2)\) there is a constant \(C(\Delta, \epsilon)>0\) such that \(t_{\text{mix}}(G,\epsilon)-t_{\text{mix}}(G,1-\epsilon)\leq C(\Delta,\epsilon)\sqrt{\log \vert V_{n}\vert}\). Finally, the authors show that \(t_{\text{mix}}(G,1/4)\) is of order of magnitude \(\log \vert V_{n}\vert\). To give a little idea of the proof we note that the mixing time can be described in terms of a random walk on an auxiliary infinite random graph which the authors call a quasi-tree and using entropy arguments. The authors also discuss limited potential for weakening the assumption that \(\Delta\) is constant.