The number of matchings in random graphs
The number of matchings in random graphs
复制标题
DOI：
10.1088/1742-5468/2006/05/p05003
复制
发表时间：
2006-05-01
影响因子：
2.4
通讯作者：
Mezard, Marc
中科院分区：
文献类型：
--
作者：
Zdeborova, Lenka;Mezard, Marc
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.
