Counting perfect matchings and the switch chain

DOI10.1137/18M1172910zbMATH Open1432.05053arXiv1705.05790OpenAlexW2963972320WikidataQ127566627 ScholiaQ127566627MaRDI QIDQ5232145FDOQ5232145

Authors: Martin Dyer, Haiko Müller 

Publication date: 29 August 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of nonbipartite graphs. In particular, we consider the switch Markov chain of Diaconis, Graham and Holmes. We determine the largest hereditary class for which the chain is ergodic, and define a large new hereditary class of graphs for which it is rapidly mixing. We go on to show that the chain has exponential mixing time for a slightly larger class. We also examine the question of ergodicity of the switch chain in a arbitrary graph. Finally, we give exact counting algorithms for three classes.

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

Recommendations

• On the switch Markov chain for perfect matchings
• On the switch Markov chain for perfect matchings
• Graph classes and the switch Markov chain for matchings
• On counting perfect matchings in general graphs
• Exact sampling from perfect matchings of dense regular bipartite graphs

zbMATH Keywords

Markov chainsapproximate countingmatchingshereditary graph classes

Mathematics Subject Classification ID

Nonparametric statistical resampling methods (62G09) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Statistical problems involving permutations with restricted positions
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Graph Classes: A Survey
• The complexity of computing the permanent
• Random generation of combinatorial structures from a uniform distribution
• Complement reducible graphs
• Algorithmic graph theory and perfect graphs
• Title not available (Why is that?)
• Undirected connectivity in log-space
• The strong perfect graph theorem
• Characterizations of strongly chordal graphs
• Bipartite permutation graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Treewidth. Computations and approximations
• Title not available (Why is that?)
• Approximating the Permanent
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• A simple linear time algorithm for cograph recognition
• Interval bigraphs and circular arc graphs
• Approximating the permanent of graphs with large factors
• Even-hole-free graphs: A survey
• On counting perfect matchings in general graphs
• Characterizing intersection classes of graphs
• On the switch Markov chain for perfect matchings
• Counting the number of matchings in chordal and chordal bipartite graph classes
• Graph classes and the switch Markov chain for matchings
• Quasimonotone graphs

Cited In (7)

• Antichains, the stick principle, and a matching number
• Geometric bounds on the fastest mixing Markov chain
• Quasimonotone graphs
• On the switch Markov chain for perfect matchings
• On the switch Markov chain for perfect matchings
• The Perfect Matching Reconfiguration Problem
• Efficient generation of random derangements with the expected distribution of cycle lengths

This page was built for publication: Counting perfect matchings and the switch chain

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