On the switch Markov chain for perfect matchings

DOI10.1137/1.9781611974331.CH138MaRDI QIDQ4575722zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

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
• Sampling weighted perfect matchings on the square-octagon lattice
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• 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)