The number of matchings in random graphs

DOI10.1088/1742-5468/2006/05/P05003zbMath1456.05153arXivcond-mat/0603350OpenAlexW2033718639MaRDI QIDQ5239288

Marc Mézard, Lenka Zdeborová

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) 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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Aggregation models on hypergraphs, Finite-size corrections for the attractive mean-field monomer-dimer model, Core structure: the coupling failure procedure in multiplex networks, Matchings on infinite graphs, \(1/n\) expansion for the number of matchings on regular graphs and Monomer-Dimer entropy, Existence of absolutely continuous spectrum for Galton-Watson random trees, A local algorithm and its percolation analysis of bipartite z-matching problem, Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results, ESTIMATING AND ENHANCING THE FEEDBACKABILITY OF COMPLEX NETWORKS, Two faces of greedy leaf removal procedure on graphs, Random-link matching problems on random regular graphs, Next nearest neighbour Ising models on random graphs, Typical performance of approximation algorithms for NP-hard problems, Two populations mean-fields monomer-dimer model, Monomer-dimer problem on random planar honeycomb lattice, Maximum matchings in scale-free networks with identical degree distribution, A mean-field monomer-dimer model with attractive interaction: Exact solution and rigorous results, Pfaffian orientations and perfect matchings of scale-free networks, Exact controllability of multiplex networks, Minimal contagious sets in random regular graphs, Inverse problem for the mean-field monomer-dimer model with attractive interaction

Cites Work

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