The number of matchings in random graphs
From MaRDI portal
Publication:5239288
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
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 (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)- A central limit theorem for the matching number of a sparse random graph
- Counting matchings in graphs
- scientific article; zbMATH DE number 3777557 (Why is no real title available?)
- Maximum matchings in a class of random graphs
- Exact matching of random graphs with constant correlation
- 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
- Two faces of greedy leaf removal procedure on graphs
- Central limit theorem in disordered monomer-dimer model
- 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 normalized matching property in random and pseudorandom bipartite graphs
- Finite-size corrections for the attractive mean-field monomer-dimer model
- The number of perfect matchings, and the nesting properties, of random regular graphs
- Core structure: the coupling failure procedure in multiplex networks
- Inverse problem for the mean-field monomer-dimer model with attractive interaction
- scientific article; zbMATH DE number 4073029 (Why is no real title available?)
- ESTIMATING AND ENHANCING THE FEEDBACKABILITY OF COMPLEX NETWORKS
- A mean-field monomer-dimer model with attractive interaction: exact solution and rigorous results
- The matching energy of random graphs
- scientific article; zbMATH DE number 6960780 (Why is no real title available?)
- Monomer-dimer problem on random planar honeycomb lattice
- Small maximal matchings in random graphs.
- Matchings in random biregular bipartite graphs
- Random multi-index matching problems
- Minimal contagious sets in random regular graphs
- Existence of absolutely continuous spectrum for Galton-Watson random trees
- Random-link matching problems on random regular graphs
- Pfaffian orientations and perfect matchings of scale-free networks
- 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)
