On the switch Markov chain for perfect matchings

DOI10.1137/1.9781611974331.CH138zbMATH Open1412.60105arXiv1501.07725OpenAlexW2950321316WikidataQ59895106 ScholiaQ59895106MaRDI QIDQ4575722FDOQ4575722

Authors: Martin Dyer, Haiko Müller, Mark Jerrum 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possible approach to a sampling problem arising in Statistics. We ask: for which classes of graphs is the Markov chain ergodic and for which is it rapidly mixing? We provide a precise answer to the ergodicity question and close bounds on the mixing question. We show for the first time that the mixing time of the switch chain is polynomial in the case of monotone graphs, a class that includes examples of interest in the statistical setting.

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

Recommendations

• On the switch Markov chain for perfect matchings
• Graph classes and the switch Markov chain for matchings
• Counting perfect matchings and the switch chain
• Perfect matchings in the semirandom graph process
• Mixing time of the switch Markov chain and stable degree sequences
• scientific article; zbMATH DE number 2189776
• On random exchange-stable matchings
• Rapid mixing of the switch Markov chain for strongly stable degree sequences
• Perfect matchings in random polyomino chain graphs
• Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Dynamical systems and their relations with probability theory and stochastic processes (37A50)

Cited In (12)

• Randomized sequential importance sampling for estimating the number of perfect matchings in bipartite graphs
• Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
• Efficient, local and symmetric Markov chains that generate one-factorizations
• The Effect of Boundary Conditions on Mixing Rates of Markov Chains
• Graph classes and the switch Markov chain for matchings
• Counting perfect matchings and the switch chain
• Quasimonotone graphs
• Sampling weighted perfect matchings on the square-octagon lattice
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• Sampling weighted perfect matchings on the square-octagon lattice
• Cutoff for rewiring dynamics on perfect matchings
• On the switch Markov chain for perfect matchings

This page was built for publication: On the switch Markov chain for perfect matchings

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