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 条

[11] Spin glass models with ferromagnetically biased couplings on the Bethe lattice: analytic solutions and numerical simulations [J].

Castellani, T ;

Krzakala, F ;

Ricci-Tersenghi, F .

EUROPEAN PHYSICAL JOURNAL B, 2005, 47 (01) :99-108

[12]

CHIEN S, 2004, P 15 ANN ACM SIAM S, P728

[13] Rigorous decimation-based construction of ground pure states for spin-glass models on random lattices [J].

Cocco, S ;

Dubois, O ;

Mandler, J ;

Monasson, R .

PHYSICAL REVIEW LETTERS, 2003, 90 (04) :4-472054

[14] Replica bounds for optimization problems and diluted spin systems [J].

Franz, S ;

Leone, M .

JOURNAL OF STATISTICAL PHYSICS, 2003, 111 (3-4) :535-564

[15] Replica bounds for diluted non-Poissonian spin systems [J].

Franz, S ;

Leone, M ;

Toninelli, FL .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2003, 36 (43) :10967-10985

[16]

FRIEZE A, 2003, ACM SIAM S DISCRETE, P148

[17]

FURER M, 2005, SIAM P ALENEX ANALCO

[18]

Gamarnik D, 2004, LECT NOTES COMPUT SC, V3122, P357

[19] Broken replica symmetry bounds in the mean field spin glass model [J].

Guerra, F .

COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2003, 233 (01) :1-12

[20]

HARRIS AB, 2004, CONDMAT0408618

← 1 2 3 4 5 →