The number of matchings in random graphs

DOI10.1088/1742-5468/2006/05/P05003MaRDI QIDQ5239288zbMATHOpenAlexFDO

Authors Lenka Zdeborová, Marc Mézard

Publication date 22 October 2019

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0603350

zbMATH Keywords

networksrandom graphsmessage-passing algorithmscavity and replica method

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Abstract: We study matchings on sparse random graphs by means of the cavity method. We first show how the method reproduces several known results about maximum and perfect matchings in regular and Erdos-Renyi random graphs. Our main new result is the computation of the entropy, i.e. the leading order of the logarithm of the number of solutions, of matchings with a given size. We derive both an algorithm to compute this entropy for an arbitrary graph with a girth that diverges in the large size limit, and an analytic result for the entropy in regular and Erdos-Renyi random graph ensembles.

Recommendations

• Small maximal matchings in random graphs.
• scientific article; zbMATH DE number 1139976
• Matching algorithms are fast in sparse random graphs
• Random matchings in regular graphs
• The number of matchings in random regular graphs and bipartite graphs

Cites work

• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1139976 (Why is no real title available?)
• scientific article; zbMATH DE number 1952026 (Why is no real title available?)
• scientific article; zbMATH DE number 2079334 (Why is no real title available?)
• A determinant-based algorithm for counting perfect matchings in a general graph
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Approximation algorithms for NP-hard problems.
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Broken replica symmetry bounds in the mean field spin glass model
• Coloring random graphs
• Counting without sampling
• Factor graphs and the sum-product algorithm
• Matching theory
• On the number of circuits in random graphs
• Phase Transitions in Combinatorial Optimization Problems
• Random multi-index matching problems
• Replica bounds for diluted non-Poissonian spin systems
• Replica bounds for optimization problems and diluted spin systems
• The \(\zeta(2)\) limit in the random assignment problem
• The cavity method at zero temperature
• The complexity of computing the permanent
• The number of matchings in random regular graphs and bipartite graphs
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Threshold values of random K‐SAT from the cavity method
• Two solutions to diluted \(p\)-spin models and XORSAT problems

Cited in

(37)

• The number of perfect matchings, and the nesting properties, of random regular graphs
• Existence of absolutely continuous spectrum for Galton-Watson random trees
• Monomer-dimer problem on random planar honeycomb lattice
• Aggregation models on hypergraphs
• scientific article; zbMATH DE number 6960780 (Why is no real title available?)
• Counting matchings in graphs
• Typical performance of approximation algorithms for NP-hard problems
• Finite-size corrections for the attractive mean-field monomer-dimer model
• A mean-field monomer-dimer model with attractive interaction: exact solution and rigorous results
• The normalized matching property in random and pseudorandom bipartite graphs
• Small maximal matchings in random graphs.
• Random matchings in regular graphs
• ESTIMATING AND ENHANCING THE FEEDBACKABILITY OF COMPLEX NETWORKS
• Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
• Maximum matchings in a class of random graphs
• Pfaffian orientations and perfect matchings of scale-free networks
• Core structure: the coupling failure procedure in multiplex networks
• Random multi-index matching problems
• On the number of circuits in random graphs
• Matchings in random biregular bipartite graphs
• Exact controllability of multiplex networks
• Minimal contagious sets in random regular graphs
• Matchings and cycle covers in random digraphs
• Next nearest neighbour Ising models on random graphs
• scientific article; zbMATH DE number 3777557 (Why is no real title available?)
• Exact matching of random graphs with constant correlation
• A local algorithm and its percolation analysis of bipartite z-matching problem
• Inverse problem for the mean-field monomer-dimer model with attractive interaction
• Matchings on infinite graphs
• scientific article; zbMATH DE number 4073029 (Why is no real title available?)
• Maximum matchings in scale-free networks with identical degree distribution
• The matching energy of random graphs
• The guessing number of undirected graphs
• \(1/n\) expansion for the number of matchings on regular graphs and Monomer-Dimer entropy
• Two faces of greedy leaf removal procedure on graphs
• Two populations mean-fields monomer-dimer model
• Random-link matching problems on random regular graphs

This page was built for publication: The number of matchings in random graphs

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