Decay of correlations for the hardcore model on the d-regular random graph

被引:8
作者
Bhatnagar, Nayantara [1 ]
Sly, Allan [2 ]
Tetali, Prasad [3 ]
机构
[1] Univ Delaware, Newark, DE 19716 USA
[2] Univ Calif Berkeley, Berkeley, CA 94720 USA
[3] Georgia Inst Technol, Atlanta, GA 30332 USA
关键词
reconstruction; threshold; hardcore model; random regular graph; decay of correlations; Gibbs measure; RECONSTRUCTION; TREES; INDEPENDENCE;
D O I
10.1214/16-EJP3552
中图分类号
O21 [概率论与数理统计]; C8 [统计学];
学科分类号
020208 ; 070103 ; 0714 ;
摘要
A key insight from statistical physics about spin systems on random graphs is the central role played by Gibbs measures on trees. We determine the local weak limit of the hardcore model on random regular graphs upto a density for the largest independent set that is bounded by and goes asymptotically to the condensation threshold. We show that the hardcore measure converges in probability locally in a strong sense to the free boundary condition Gibbs measure on the tree. As a consequence we show that the reconstruction threshold on the random graph, indicative of the onset of point to set spatial correlations, is equal to the reconstruction threshold on the d-regular tree for which we determine precise asymptotics. We expect that our methods will generalize to a wide range of spin systems for which the second moment method holds.
引用
收藏
页数:42
相关论文
共 40 条
[1]   Algorithmic Barriers from Phase Transitions [J].
Achlioptas, Dimitris ;
Coja-Oghlan, Amin .
PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, :793-+
[2]  
Bapst V., 2014, PREPRINT
[3]   The hard-core model on random graphs revisited [J].
Barbier, Jean ;
Krzakala, Florent ;
Zdeborova, Lenka ;
Zhang, Pan .
ELC INTERNATIONAL MEETING ON INFERENCE, COMPUTATION, AND SPIN GLASSES (ICSG2013), 2013, 473
[4]   Glauber dynamics on trees and hyperbolic graphs [J].
Berger, N ;
Kenyon, C ;
Mossel, E ;
Peres, Y .
PROBABILITY THEORY AND RELATED FIELDS, 2005, 131 (03) :311-340
[5]   RECONSTRUCTION FOR COLORINGS ON TREES [J].
Bhatnagar, Nayantara ;
Vera, Juan ;
Vigoda, Eric ;
Weitz, Dror .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) :809-826
[6]  
Bhatnagar N, 2010, LECT NOTES COMPUT SC, V6302, P434, DOI 10.1007/978-3-642-15369-3_33
[7]   ON THE PURITY OF THE LIMITING GIBBS STATE FOR THE ISING-MODEL ON THE BETHE LATTICE [J].
BLEHER, PM ;
RUIZ, J ;
ZAGREBNOV, VA .
JOURNAL OF STATISTICAL PHYSICS, 1995, 79 (1-2) :473-482
[8]  
Bollobs B., 1980, Eur. J. Comb., V1, P311, DOI DOI 10.1016/S0195-6698(80)80030-8
[9]  
Borgs C, 2006, ANN IEEE SYMP FOUND, P518
[10]   A second threshold for the hard-core model on a Bethe lattice [J].
Brightwell, GR ;
Winkler, P .
RANDOM STRUCTURES & ALGORITHMS, 2004, 24 (03) :303-314