The number of matchings in random graphs

DOI10.1088/1742-5468/2006/05/P05003zbMATH Open1456.05153arXivcond-mat/0603350OpenAlexW2033718639MaRDI QIDQ5239288FDOQ5239288

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)

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.

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

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

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)

Cites Work

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

Cited In (36)

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

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)