Cutoff for Rewiring Dynamics on Perfect Matchings

Abstract

We establish cutoff for a natural random walk (RW) on the set of perfect matchings (PMs). An $n$-PM is a pairing of $2n$ objects. The $k$-PM RW selects $k$ pairs uniformly at random, disassociates the corresponding $2k$ objects, then chooses a new pairing on these $2k$ objects uniformly at random. The equilibrium distribution is uniform over the set of all $n$-PM. We establish cutoff for the $k$-PM RW whenever $2\le k\ll n$. If $k\gg 1$, then the mixing time is $\frac{n}{k}\log n$ to leading order. The case $k=2$ was established by Diaconis and Holmes (2002) by relating the $2$-PM RW to the random transpositions card shuffle and also by Ceccherini-Silberstein, Scarabotti and Tolli (2007, 2008) using representation theory. We are the first to handle $k>2$. Our argument builds on previous work of Berestycki, Schramm, Şengül and Zeitouni (2005, 2011, 2019) regarding conjugacy-invariant RWs on the permutation group.

v2. 30 pages; 5 figures. Improvements to the presentation suggested by anonymous referee. To appear in AAP

References in corpus (3)

• The mixing time of the switch Markov chains: a unified approach
• Limit Profiles for Reversible Markov Chains
• The interchange process with reversals on the complete graph

Cited by in corpus (1)

• Mixing of fast random walks on dynamic random permutations