A rigorous proof of the cavity method for counting matchings

Simple item page
dc.creatorBayati, Mohsen
dc.creatorNair, Chandra
dc.date2006-07-11
dc.date2006-07-17
dc.date.accessioned2026-07-07T07:15:57Z
dc.date.available2026-07-07T07:15:57Z
dc.descriptionIn 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.
dc.description11 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/cond-mat/0607290
dc.identifierhttp://arxiv.org/abs/cond-mat/0607290
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/113410
dc.subjectDisordered Systems and Neural Networks
dc.subjectStatistical Mechanics
dc.subjectComputational Complexity
dc.titleA rigorous proof of the cavity method for counting matchings
dc.typetext

Files

Collections

arXiv