Right-convergence of sparse random graphs
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 GN,N≥1 to some target graph W . The theory of dense graph convergence, including random dense graphs, i...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer Berlin Heidelberg
2014
|
| Online Access: | http://hdl.handle.net/1721.1/87698 https://orcid.org/0000-0001-8898-8778 |
| _version_ | 1826210590918443008 |
|---|---|
| author | Gamarnik, David |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Gamarnik, David |
| author_sort | Gamarnik, David |
| collection | MIT |
| description | 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 GN,N≥1 to some target graph W . 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; Lovász 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 W . In this paper we prove that the sequence of sparse Erdös-Rényi graphs is right-converging when the tensor product associated with the target graph W satisfies a certain convexity property. We treat the case of discrete and continuous target graphs W . 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 RN by intersecting it with linearly in N 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 Erdös-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 Erdös-Rényi graphs for some special cases of W . 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. |
| first_indexed | 2024-09-23T14:52:23Z |
| format | Article |
| id | mit-1721.1/87698 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:52:23Z |
| publishDate | 2014 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/876982022-09-29T11:05:50Z Right-convergence of sparse random graphs Gamarnik, David Sloan School of Management Gamarnik, David 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 GN,N≥1 to some target graph W . 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; Lovász 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 W . In this paper we prove that the sequence of sparse Erdös-Rényi graphs is right-converging when the tensor product associated with the target graph W satisfies a certain convexity property. We treat the case of discrete and continuous target graphs W . 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 RN by intersecting it with linearly in N 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 Erdös-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 Erdös-Rényi graphs for some special cases of W . 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. National Science Foundation (U.S.) (NSF grant CMMI-1031332) 2014-06-09T15:09:38Z 2014-06-09T15:09:38Z 2013-09 2013-08 Article http://purl.org/eprint/type/JournalArticle 0178-8051 1432-2064 http://hdl.handle.net/1721.1/87698 Gamarnik, David. “Right-Convergence of Sparse Random Graphs.” Probability Theory and Related Fields (September 14, 2013). https://orcid.org/0000-0001-8898-8778 en_US http://dx.doi.org/10.1007/s00440-013-0528-6 Probability Theory and Related Fields Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Berlin Heidelberg arXiv |
| spellingShingle | Gamarnik, David Right-convergence of sparse random graphs |
| title | Right-convergence of sparse random graphs |
| title_full | Right-convergence of sparse random graphs |
| title_fullStr | Right-convergence of sparse random graphs |
| title_full_unstemmed | Right-convergence of sparse random graphs |
| title_short | Right-convergence of sparse random graphs |
| title_sort | right convergence of sparse random graphs |
| url | http://hdl.handle.net/1721.1/87698 https://orcid.org/0000-0001-8898-8778 |
| work_keys_str_mv | AT gamarnikdavid rightconvergenceofsparserandomgraphs |