Counting perfect matchings and the switch chain

DOI10.1137/18M1172910MaRDI QIDQ5232145zbMATHOpenAlexWikidataFDO

Authors Martin Dyer, Haiko Müller

Publication date 29 August 2019

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

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

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)

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.

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

Cites work

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

Cited in

(7)

• Antichains, the stick principle, and a matching number
• The Perfect Matching Reconfiguration Problem
• On the switch Markov chain for perfect matchings
• On the switch Markov chain for perfect matchings
• Geometric bounds on the fastest mixing Markov chain
• Quasimonotone graphs
• 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)