The number of matchings in random graphs

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.

17 pages, 6 figures, to be published in Journal of Statistical Mechanics

References in corpus (4)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• On the number of circuits in random graphs
• Maximum matching on random graphs
• Dimer Statistics on a Bethe Lattice

Cited by in corpus (57)

• Control Principles of Complex Networks
• Exact Controllability of Complex Networks
• Emergence of bimodality in controlling complex networks
• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• Core percolation on complex networks
• Controllability of multiplex, multi-timescale networks
• Control of Multilayer Networks
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Constraint satisfaction problems with isolated solutions are hard
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• Minimal contagious sets in random regular graphs
• Controllability and maximum matchings of complex networks
• The rank of diluted random graphs
• Irrelevance of linear controllability to nonlinear dynamical networks
• Structure controllability of complex network based on preferential matching
• The stochastic matching problem
• An efficient algorithm for finding all possible input nodes for controlling complex networks
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• When a local Hamiltonian must be frustration-free
• Input graph: the hidden geometry in controlling complex networks
• A rigorous proof of the cavity method for counting matchings
• A mean-field monomer-dimer model with attractive interaction. The exact solution
• Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
• Stochastic optimization by message passing
• Statistical mechanics of dimers on quasiperiodic Ammann-Beenker tilings
• Ground-State Entropy of the Random Vertex-Cover Problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• The evolution of network controllability in growing networks
• Aggregation models on hypergraphs
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
• Maximum matchings in scale-free networks with identical degree distribution
• One-loop diagrams in the Random Euclidean Matching Problem
• Recovery thresholds in the sparse planted matching problem
• Fluctuations in the random-link matching problem
• Two faces of greedy leaf removal procedure on graphs
• Clustering in Hilbert space of a quantum optimization problem
• Cavity approach to the Sourlas code system
• Next nearest neighbour Ising models on random graphs
• Spin glass phase transitions in the random feedback vertex set problem
• Random-link matching problems on random regular graphs
• Inverse problem for the mean-field monomer-dimer model with attractive interaction
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• Matchings on infinite graphs
• The Random Fractional Matching Problem
• Solvable Metric Growing Networks
• Phase transition in the controllability of temporal networks
• Counting maximal near perfect matchings in quasirandom and dense graphs
• Phase transition in the bipartite z-matching
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• One-in-Two-Matching Problem is NP-complete
• Errata and Addenda to Mathematical Constants
• Finite-size corrections for the attractive mean-field monomer-dimer model
• Step-wise target controllability identifies dysregulated pathways of macrophage networks in multiple sclerosis
• Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm