Right-convergence of sparse random graphs

• 成果类型: Article
• 署名作者: Gamarnik, David
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-013-0528-6
• 发表日期: 2014
• 页码: 253-278
• 关键词: replica bounds; SEQUENCES

摘要

The paper is devoted to the problem of establishing right-convergence of sparse random graphs. This concerns the convergence of the logarithm of number of homomorphisms from graphs or hyper-graphs to some target graph . The theory of dense graph convergence, including random dense graphs, is now well understood (Borgs et al. in Ann Math 176:151-219, 2012; Borgs et al. in Adv Math 219:1801-1851, 2008; Chatterjee and Varadhan in Eur J Comb 32:1000-1017, 2011; Lovasz and Szegedy in J Comb Theory Ser B 96:933-957, 2006), but its counterpart for sparse random graphs presents some fundamental difficulties. Phrased in the statistical physics terminology, the issue is the existence of the limits of appropriately normalized log-partition functions, also known as free energy limits, for the Gibbs distribution associated with . In this paper we prove that the sequence of sparse Erdos-R,nyi graphs is right-converging when the tensor product associated with the target graph satisfies a certain convexity property. We treat the case of discrete and continuous target graphs . The latter case allows us to prove a special case of Talagrand's recent conjecture [more accurately stated as level III Research Problem 6.7.2 in his recent book (Talagrand in Mean Field Models for Spin Glasses: Volume I: Basic examples. Springer, Berlin, 2010)], concerning the existence of the limit of the measure of a set obtained from by intersecting it with linearly in many subsets, generated according to some common probability law. Our proof is based on the interpolation technique, introduced first by Guerra and Toninelli (Commun Math Phys 230:71-79, 2002) and developed further in (Abbe and Montanari in On the concentration of the number of solutions of random satisfiability formulas, 2013; Bayati et al. in Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010; Contucci et al. in Antiferromagnetic Potts model on the Erdos-R,nyi random graph, 2011; Franz and Leone in J Stat Phys 111(3/4):535-564, 2003; Franz et al. in J Phys A Math Gen 36:10967-10985, 2003; Montanari in IEEE Trans Inf Theory 51(9):3221-3246, 2005; Panchenko and Talagrand in Probab Theory Relat Fields 130:312-336, 2004). Specifically, Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) establishes the right-convergence property for Erdos-R,nyi graphs for some special cases of . In this paper most of the results in Bayati et al. (Ann Probab Conference version in Proceedings of 42nd Ann. Symposium on the Theory of Computing (STOC), 2010) follow as a special case of our main theorem.