The number of matchings in random graphs

DOI10.1088/1742-5468/2006/05/P05003MaRDI QIDQ5239288zbMATH OpenOpenAlexFDO

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

cavity and replica methodmessage-passing algorithmsnetworksrandom graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) 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

• 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
• 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?)
• 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 (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

(39)

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

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)