Cutoff for Rewiring Dynamics on Perfect Matchings
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929348886396928 |
|---|---|
| author | Olesker-Taylor, Sam |
| author_facet | Olesker-Taylor, Sam |
| contents | 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 $\tfrac nk \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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_11890 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Cutoff for Rewiring Dynamics on Perfect Matchings Olesker-Taylor, Sam Probability Combinatorics 60B15, 60C05, 60J10, 60J90 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 $\tfrac nk \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. |
| title | Cutoff for Rewiring Dynamics on Perfect Matchings |
| topic | Probability Combinatorics 60B15, 60C05, 60J10, 60J90 |
| url | https://arxiv.org/abs/2108.11890 |