Cutoff for rewiring dynamics on perfect matchings

DOI10.1214/22-AAP1825MaRDI QIDQ6103979zbMATH OpenOpenAlexFDO

Authors

Publication date 5 June 2023

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.11890

zbMATH Keywords

cutoffperfect matchingsrandom walksmixing timecoalescence-fragmentationrandom transpositionsconjugacy-invariant random walks

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05) Coalescent processes (60J90)

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 $2leklln$. If $kgg1$, then the mixing time is $fracnklogn$ 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, c{S}eng"ul and Zeitouni (2005, 2011, 2019) regarding conjugacy-invariant RWs on the permutation group.

Recommendations

• Universality of cutoff for graphs with an added random matching
• Random walks on trees and matchings
• Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique
• On the switch Markov chain for perfect matchings
• Cutoff for conjugacy-invariant random walks on the permutation group

Cites work

• scientific article; zbMATH DE number 1334601 (Why is no real title available?)
• scientific article; zbMATH DE number 6472593 (Why is no real title available?)
• scientific article; zbMATH DE number 6472599 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Compositions of random transpositions
• Cutoff for conjugacy-invariant random walks on the permutation group
• Finite Gel'fand pairs and their applications to probability and statistics
• Harmonic analysis on finite groups. Representation theory, Gelfand pairs and Markov chains
• Limit profile for random transpositions
• Limit profiles for reversible Markov chains
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Matchings and phylogenetic trees
• Mixing times for random \(k\)-cycles and coalescence-fragmentation chains
• Mixing times of random walks on dynamic configuration models
• Poisson–Dirichlet and GEM Invariant Distributions for Split-and-Merge Transformations of an Interval Partition
• Proof of Aldous' spectral gap conjecture
• Quantum Heisenberg models and their probabilistic representations
• Random graphs and complex networks. Volume 1
• Random walks on dynamic configuration models: a trichotomy
• Random walks on trees and matchings
• Rapid mixing of the switch Markov chain for strongly stable degree sequences
• Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
• Stationary Random Partitions of Positive Integers
• The asymptotic number of labeled graphs with given degree sequences
• The cycle structure of random permutations
• The interchange process with reversals on the complete graph
• The mixing time of switch Markov chains: a unified approach
• The random k cycle walk on the symmetric group

Cited in

(1)

• Random walks on trees and matchings

This page was built for publication: Cutoff for rewiring dynamics on perfect matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103979)