An introduction to large deviations for random graphs

Chatterjee, Sourav

doi:10.1090/bull/1539

An introduction to large deviations for random graphs
HTML articles powered by AMS MathViewer

by Sourav Chatterjee PDF

Bull. Amer. Math. Soc. 53 (2016), 617-642 Request permission

Abstract:

This article gives an overview of the emerging literature on large deviations for random graphs. Written for the general mathematical audience, the article begins with a short introduction to the theory of large deviations. This is followed by a description of some large deviation questions about random graphs and an outline of the recent progress on this topic. A more elaborate discussion follows, with a brief account of graph limit theory and its application in constructing a large deviation theory for dense random graphs. The role of Szemerédi’s regularity lemma is explained, together with a sketch of the proof of the main large deviation result and some examples. Applications to exponential random graph models are briefly touched upon. The remainder of the paper is devoted to large deviations for sparse graphs. Since the regularity lemma is not applicable in the sparse regime, new tools are needed. Fortunately, there have been several new breakthroughs that managed to achieve the goal by an indirect method. These are discussed, together with an exposition of the underlying theory. The last section contains a list of open problems.

References

David J. Aldous, Representations for partially exchangeable arrays of random variables, J. Multivariate Anal. 11 (1981), no. 4, 581–598. MR 637937, DOI 10.1016/0047-259X(81)90099-3
David Aristoff and Charles Radin, Emergent structures in large networks, J. Appl. Probab. 50 (2013), no. 3, 883–888. MR 3102521, DOI 10.1239/jap/1378401243
David Aristoff and Lingjiong Zhu, Asymptotic structure and singularities in constrained directed graphs, Stochastic Process. Appl. 125 (2015), no. 11, 4154–4177. MR 3385599, DOI 10.1016/j.spa.2015.06.004
S. Bhamidi, G. Bresler and A. Sly, Mixing time of exponential random graphs, In 2008 IEEE 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008, 803–812.
B. Bhattacharya, S. Ganguly, E. Lubetzky and Y. Zhao, Upper tails and independence polynomials in random graphs. arXiv preprint arXiv:1507.04074, 2015.
Béla Bollobás and Oliver Riordan, Metrics for sparse graphs, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., vol. 365, Cambridge Univ. Press, Cambridge, 2009, pp. 211–287. MR 2588543
E. Bolthausen, F. Comets and A. Dembo, Large deviations for random matrices and random graphs, Private communication, 2003.
Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi, Counting graph homomorphisms, Topics in discrete mathematics, Algorithms Combin., vol. 26, Springer, Berlin, 2006, pp. 315–371. MR 2249277, DOI 10.1007/3-540-33700-8_{1}8
C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), no. 6, 1801–1851. MR 2455626, DOI 10.1016/j.aim.2008.07.008
C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, Convergent sequences of dense graphs II. Multiway cuts and statistical physics, Ann. of Math. (2) 176 (2012), no. 1, 151–219. MR 2925382, DOI 10.4007/annals.2012.176.1.2
C. Borgs, J. T. Chayes, H. Cohn and Y. Zhao, An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions. arXiv preprint arXiv:1401.2906, 2014.
C. Borgs, J. T. Chayes, H. Cohn and Y. Zhao, An $L^p$ theory of sparse graph convergence II: LD convergence, quotients, and right convergence. arXiv preprint arXiv:1408.0744, 2014.
Gioia Carinci, Jean-René Chazottes, Cristian Giardinà, and Frank Redig, Nonconventional averages along arithmetic progressions and lattice spin systems, Indag. Math. (N.S.) 23 (2012), no. 3, 589–602. MR 2948646, DOI 10.1016/j.indag.2012.05.010
Sourav Chatterjee, Concentration inequalities with exchangeable pairs, ProQuest LLC, Ann Arbor, MI, 2005. Thesis (Ph.D.)–Stanford University. MR 2707160
Sourav Chatterjee, Stein’s method for concentration inequalities, Probab. Theory Related Fields 138 (2007), no. 1-2, 305–321. MR 2288072, DOI 10.1007/s00440-006-0029-y
Sourav Chatterjee, The missing log in large deviations for triangle counts, Random Structures Algorithms 40 (2012), no. 4, 437–451. MR 2925306, DOI 10.1002/rsa.20381
Chatterjee, S. and Dembo, A. (2014), Nonlinear large deviations. To appear in Adv. Math.
Sourav Chatterjee and Partha S. Dey, Applications of Stein’s method for concentration inequalities, Ann. Probab. 38 (2010), no. 6, 2443–2485. MR 2683635, DOI 10.1214/10-AOP542
Sourav Chatterjee and Persi Diaconis, Estimating and understanding exponential random graph models, Ann. Statist. 41 (2013), no. 5, 2428–2461. MR 3127871, DOI 10.1214/13-AOS1155
Sourav Chatterjee and S. R. S. Varadhan, The large deviation principle for the Erdős-Rényi random graph, European J. Combin. 32 (2011), no. 7, 1000–1017. MR 2825532, DOI 10.1016/j.ejc.2011.03.014
B. DeMarco and J. Kahn, Upper tails for triangles, Random Structures Algorithms 40 (2012), no. 4, 452–459. MR 2925307, DOI 10.1002/rsa.20382
B. Demarco and J. Kahn, Tight upper tail bounds for cliques, Random Structures Algorithms 41 (2012), no. 4, 469–487. MR 2993131, DOI 10.1002/rsa.20440
Amir Dembo and Ofer Zeitouni, Large deviations techniques and applications, Stochastic Modelling and Applied Probability, vol. 38, Springer-Verlag, Berlin, 2010. Corrected reprint of the second (1998) edition. MR 2571413, DOI 10.1007/978-3-642-03311-7
Persi Diaconis and Svante Janson, Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7) 28 (2008), no. 1, 33–61. MR 2463439
P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175–220. MR 1723039, DOI 10.1007/s004930050052
D. N. Hoover, Row-column exchangeability and a generalized model for probability, Exchangeability in probability and statistics (Rome, 1981) North-Holland, Amsterdam-New York, 1982, pp. 281–291. MR 675982
Svante Janson, Krzysztof Oleszkiewicz, and Andrzej Ruciński, Upper tails for subgraph counts in random graphs, Israel J. Math. 142 (2004), 61–92. MR 2085711, DOI 10.1007/BF02771528
Olav Kallenberg, Probabilistic symmetries and invariance principles, Probability and its Applications (New York), Springer, New York, 2005. MR 2161313
R. Kenyon, C. Radin, K. Ren and L. Sadun, Multipodal Structure and Phase Transitions in Large Constrained Graphs. arXiv preprint arXiv:1405.0599, (2014).
R. Kenyon M. Yin, On the asymptotics of constrained exponential random graphs. arXiv preprint arXiv:1406.3662, 2014.
Yuri Kifer, Nonconventional limit theorems, Probab. Theory Related Fields 148 (2010), no. 1-2, 71–106. MR 2653222, DOI 10.1007/s00440-009-0223-9
Yuri Kifer and S. R. S. Varadhan, Nonconventional limit theorems in discrete and continuous time via martingales, Ann. Probab. 42 (2014), no. 2, 649–688. MR 3178470, DOI 10.1214/12-AOP796
Yuri Kifer and S. R. S. Varadhan, Nonconventional large deviations theorems, Probab. Theory Related Fields 158 (2014), no. 1-2, 197–224. MR 3152784, DOI 10.1007/s00440-013-0481-4
Jeong Han Kim and Van H. Vu, Concentration of multivariate polynomials and its applications, Combinatorica 20 (2000), no. 3, 417–434. MR 1774845, DOI 10.1007/s004930070014
J. H. Kim and V. H. Vu, Divide and conquer martingales and the number of triangles in a random graph, Random Structures Algorithms 24 (2004), no. 2, 166–174. MR 2035874, DOI 10.1002/rsa.10113
RafałLatała, Estimation of moments of sums of independent real random variables, Ann. Probab. 25 (1997), no. 3, 1502–1513. MR 1457628, DOI 10.1214/aop/1024404522
László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035, DOI 10.1090/coll/060
László Lovász and Balázs Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933–957. MR 2274085, DOI 10.1016/j.jctb.2006.05.002
E. Lubetzky and Y. Zhao, On the variational problem for upper tails of triangle counts in sparse random graphs. arXiv preprint arXiv:1402.6011, 2014.
Eyal Lubetzky and Yufei Zhao, On replica symmetry of large deviations in random graphs, Random Structures Algorithms 47 (2015), no. 1, 109–146. MR 3366814, DOI 10.1002/rsa.20536
Charles Radin, Kui Ren, and Lorenzo Sadun, The asymptotics of large constrained graphs, J. Phys. A 47 (2014), no. 17, 175001, 20. MR 3197554, DOI 10.1088/1751-8113/47/17/175001
Charles Radin and Lorenzo Sadun, Phase transitions in a complex network, J. Phys. A 46 (2013), no. 30, 305002, 12. MR 3083277, DOI 10.1088/1751-8113/46/30/305002
Charles Radin and Lorenzo Sadun, Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys. 158 (2015), no. 4, 853–865. MR 3311483, DOI 10.1007/s10955-014-1151-3
Charles Radin and Mei Yin, Phase transitions in exponential random graphs, Ann. Appl. Probab. 23 (2013), no. 6, 2458–2471. MR 3127941, DOI 10.1214/12-AAP907
Cosma Rohilla Shalizi and Alessandro Rinaldo, Consistency under sampling of exponential random graph models, Ann. Statist. 41 (2013), no. 2, 508–535. MR 3099112, DOI 10.1214/12-AOS1044
Endre Szemerédi, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) Colloq. Internat. CNRS, vol. 260, CNRS, Paris, 1978, pp. 399–401 (English, with French summary). MR 540024
Michel Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes Études Sci. Publ. Math. 81 (1995), 73–205. MR 1361756
Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
V. H. Vu, Concentration of non-Lipschitz functions and applications, Random Structures Algorithms 20 (2002), no. 3, 262–316. Probabilistic methods in combinatorial optimization. MR 1900610, DOI 10.1002/rsa.10032
Mei Yin, Critical phenomena in exponential random graphs, J. Stat. Phys. 153 (2013), no. 6, 1008–1021. MR 3131507, DOI 10.1007/s10955-013-0874-x
Y. Zhao, On the lower tail variational problem for random graphs. arXiv preprint arXiv:1502.00867, 2015.