A rigorous proof of the cavity method for counting matchings

Abstract

In this paper we rigorously prove the validity of the cavity method for the problem of counting the number of matchings in graphs with large girth. Cavity method is an important heuristic developed by statistical physicists that has lead to the development of faster distributed algorithms for problems in various combinatorial optimization problems. The validity of the approach has been supported mostly by numerical simulations. In this paper we prove the validity of cavity method for the problem of counting matchings using rigorous techniques. We hope that these rigorous approaches will finally help us establish the validity of the cavity method in general.

11 pages, 1 figure

References in corpus (3)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of matchings in random graphs
• A CDMA multiuser detection algorithm based on survey propagation

Cited by in corpus (7)

• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• Approximating the Permanent with Fractional Belief Propagation
• Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
• The correlation decay (CD) tree and strong spatial mixing in multi-spin systems
• The cavity method for counting spanning subgraphs subject to local constraints
• Matchings on infinite graphs
• Bounding the Bethe and the Degree-$M$ Bethe Permanents