The number of matchings in random graphs

被引：88

作者：

Zdeborova, Lenka ^{[1
]}

Mezard, Marc ^{[1
]}

机构：

[1] Univ Paris 11, CNRS, UMR 8626, LPTMS, F-91405 Orsay, France

来源：

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2006年

关键词：

cavity and replica method; message-passing algorithms; random graphs; networks;

D O I：

10.1088/1742-5468/2006/05/P05003

中图分类号：

O3 [力学];

学科分类号：

08 ; 0801 ;

摘要：

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.

引用

页数：24

共 49 条

[1] The ζ(2) limit in the random assignment problem [J].

Aldous, DJ .

RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (04) :381-418

[2]

[Anonymous], P 22 IEEE ANN S FDN

[3]

[Anonymous], 1987, WORLD SCI LECT NOTES

[4]

Aronson J, 1998, RANDOM STRUCT ALGOR, V12, P111, DOI 10.1002/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO

[5]

2-#

[6]

BANDYOPADHYAY A, 2006, ACMSIAM S DISCR ALG, P890

[7] Core percolation in random graphs: a critical phenomena analysis [J].

Bauer, M ;

Golinelli, O .

EUROPEAN PHYSICAL JOURNAL B, 2001, 24 (03) :339-352

[8]

Bayati M, 2005, 2005 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), VOLS 1 AND 2, P1763

[9] A variational description of the ground state structure in random satisfiability problems [J].

Biroli, G ;

Monasson, R ;

Weigt, M .

EUROPEAN PHYSICAL JOURNAL B, 2000, 14 (03) :551-568

[10] THE NUMBER OF MATCHINGS IN RANDOM REGULAR GRAPHS AND BIPARTITE GRAPHS [J].

BOLLOBAS, B ;

MCKAY, BD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (01) :80-91

← 1 2 3 4 5 →