2006/07/11 by Mohsen Bayati, Bayati, Mohsen, Chandra Nair +1
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Theory Research #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #Disordered Systems and Neural Networks (cond-mat.dis-nn) #FOS: Computer and information sciences #FOS: Physical sciences #Markov Chains and Monte Carlo Methods #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.dis-nn #cond-mat.stat-mech #cs.CC
paper · pdf · doi:10.48550/arxiv.cond-mat/0607290
11 pages, 1 figure
openalex publication_date 2006/07/11 · arxiv created 2006/07/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.