Circuits in random graphs: from local trees to global loops

被引：34

作者：

Marinari, E

Monasson, R

机构：

[1] Univ Roma La Sapienza, Dipartimento Fis, SMC INFM, I-00185 Rome, Italy

[2] Univ Roma La Sapienza, Ist Nazl Fis Nucl, I-00185 Rome, Italy

[3] ENS, CNRS, Phys Theor Lab, F-75005 Paris, France

来源：

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2004年

关键词：

spin glasses (theory); random graphs; networks;

D O I：

10.1088/1742-5468/2004/09/P09004

中图分类号：

O3 [力学];

学科分类号：

08 ; 0801 ;

摘要：

We compute the number of circuits and of loops with multiple crossings in random regular graphs. We discuss the importance of this issue for the validity of the cavity approach. On the one hand we obtain analytical results for the infinite volume limit in agreement with existing exact results. On the other hand we implement a counting algorithm, enumerate circuits at finite N, and draw some general conclusions about the finite-N behaviour of the number of circuits.

引用

页数：13

共 24 条

[1]

ALDOUS D, 2004, IN PRESS ANN APPL PR

[2] QUENCHED RANDOM GRAPHS [J].

BACHAS, C ;

DECALAN, C ;

PETROPOULOS, PMS .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1994, 27 (18) :6121-6127

[3]

BENNAIM E, 2004, CONDMAT0403453

[4] SPIN-GLASS THEORY IN THE BETHE APPROXIMATION - INSIGHTS AND PROBLEMS [J].

BOWMAN, DR ;

LEVIN, K .

PHYSICAL REVIEW B, 1982, 25 (05) :3438-3441

[5]

DEDOMINICIS C, 1989, J PHYS A-MATH GEN, V22, pL775, DOI 10.1088/0305-4470/22/16/003

[6] EXPONENTS FOR EXCLUDED VOLUME PROBLEM AS DERIVED BY WILSON METHOD [J].

DEGENNES, PG .

PHYSICS LETTERS A, 1972, A 38 (05) :339-&

[7] Evolution of networks [J].

Dorogovtsev, SN ;

Mendes, JFF .

ADVANCES IN PHYSICS, 2002, 51 (04) :1079-1187

[8]

Garmo H, 1999, RANDOM STRUCT ALGOR, V15, P43, DOI 10.1002/(SICI)1098-2418(199908)15:1<43::AID-RSA3>3.3.CO

[9]

2-J

[10]

Janson S, 2000, WIL INT S D

← 1 2 3 →