The number of matchings in random graphs

Lenka Zdeborová, Marc MézardarXiv 2006 · arXiv

Introduction

In graph theory, a matching is defined as a set of edges that do not share any common vertices. While finding a maximum matching is a polynomial-time problem, the task of counting the total number of matchings of a specific size $k$ is #P-complete, making it computationally intractable for large graphs. In their 2006 work, Lenka Zdeborová and Marc Mézard address this challenge by applying the "cavity method"—a technique from the statistical physics of disordered systems—to count matchings in sparse random graphs.

The Cavity Method and Factor Graphs

The authors treat the matching problem as a physical system of dimers, where each matching configuration corresponds to a state with a specific energy. To analyze this system, they map the original graph onto a factor graph.

Transformation of a graph into a factor graph for matching analysis.

In this representation, the edges of the original graph become variable nodes, and the vertices become constraint nodes. This bipartite structure allows the application of message-passing algorithms, specifically Belief Propagation (BP), to estimate the marginal probabilities of an edge being included in a matching.

Message Passing and Entropy

The core of the approach relies on the Replica Symmetric (RS) ansatz. In large, sparse random graphs, the local neighborhood of a node is tree-like, meaning that the neighbors of a node are effectively uncorrelated when that node is removed (the "cavity" assumption).

Cavity method message passing on a tree-like structure.

By passing messages between nodes, the algorithm converges to a consistent set of probabilities. From these, the authors calculate the "entropy density"—the logarithm of the number of possible matchings of a given size. This mapping provides a landscape of the solution space, showing how the number of configurations varies with the matching size $k$.

Results on Random Ensembles

The researchers evaluated their method on standard benchmarks, including $r$-regular and Erdős-Rényi (ER) random graphs. A key finding was the stability of the RS solution, suggesting that for these graph types, the physics-based approximation yields exact results.

For Erdős-Rényi graphs, the study reveals that entropy is distributed between a dense "core" and a peripheral tree-like structure. The method successfully reproduces the Karp-Sipser theorem for maximum matching sizes and provides a new, closed-form analytic formula for the entropy of matchings in ER graphs. Furthermore, the resulting BP algorithm operates in linear time relative to the number of edges, offering a significant speedup over traditional counting methods.

Conclusion

By bridging discrete mathematics and statistical physics, Zdeborová and Mézard demonstrated that the cavity method is a powerful tool for solving hard combinatorial counting problems. Their work not only provides practical algorithms for specific networks but also deepens the theoretical understanding of the solution space in random graph ensembles. Future work may extend these techniques to weighted matchings and more complex constraint satisfaction problems.

Summary updated

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.
BibTeX
@misc{zdeborova2006number,
  author = {Lenka Zdeborová and Marc Mézard},
  title = {{The number of matchings in random graphs}},
  year = {2006},
  eprint = {cond-mat/0603350},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cond-mat/0603350},
}
Figure