Cutoff for rewiring dynamics on perfect matchings

DOI10.1214/22-AAP1825zbMATH Open1516.60027arXiv2108.11890OpenAlexW4321503379MaRDI QIDQ6103979FDOQ6103979

Authors:

Publication date: 5 June 2023

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

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.

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

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

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)

Cites Work

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

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)