Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

An introduction to large deviations for random graphs


Author: Sourav Chatterjee
Journal: Bull. Amer. Math. Soc. 53 (2016), 617-642
MSC (2010): Primary 60F10, 05C80; Secondary 60C05, 05A20
DOI: https://doi.org/10.1090/bull/1539
Published electronically: June 24, 2016
MathSciNet review: 3544262
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] David J. Aldous, Representations for partially exchangeable arrays of random variables, J. Multivariate Anal. 11 (1981), no. 4, 581-598. MR 637937, https://doi.org/10.1016/0047-259X(81)90099-3
  • [2] David Aristoff and Charles Radin, Emergent structures in large networks, J. Appl. Probab. 50 (2013), no. 3, 883-888. MR 3102521, https://doi.org/10.1239/jap/1378401243
  • [3] David Aristoff and Lingjiong Zhu, Asymptotic structure and singularities in constrained directed graphs, Stochastic Process. Appl. 125 (2015), no. 11, 4154-4177. MR 3385599, https://doi.org/10.1016/j.spa.2015.06.004
  • [4] 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.
  • [5] B. Bhattacharya, S. Ganguly, E. Lubetzky and Y. Zhao, Upper tails and independence polynomials in random graphs. arXiv preprint arXiv:1507.04074, 2015.
  • [6] 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
  • [7] E. Bolthausen, F. Comets and A. Dembo, Large deviations for random matrices and random graphs, Private communication, 2003.
  • [8] 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, https://doi.org/10.1007/3-540-33700-8_18
  • [9] 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, https://doi.org/10.1016/j.aim.2008.07.008
  • [10] 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, https://doi.org/10.4007/annals.2012.176.1.2
  • [11] 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.
  • [12] 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.
  • [13] 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, https://doi.org/10.1016/j.indag.2012.05.010
  • [14] Sourav Chatterjee, Concentration inequalities with exchangeable pairs, ProQuest LLC, Ann Arbor, MI, 2005. Thesis (Ph.D.)-Stanford University. MR 2707160
  • [15] Sourav Chatterjee, Stein's method for concentration inequalities, Probab. Theory Related Fields 138 (2007), no. 1-2, 305-321. MR 2288072, https://doi.org/10.1007/s00440-006-0029-y
  • [16] Sourav Chatterjee, The missing log in large deviations for triangle counts, Random Structures Algorithms 40 (2012), no. 4, 437-451. MR 2925306, https://doi.org/10.1002/rsa.20381
  • [17] Chatterjee, S. and Dembo, A. (2014), Nonlinear large deviations. To appear in Adv. Math.
  • [18] Sourav Chatterjee and Partha S. Dey, Applications of Stein's method for concentration inequalities, Ann. Probab. 38 (2010), no. 6, 2443-2485. MR 2683635, https://doi.org/10.1214/10-AOP542
  • [19] Sourav Chatterjee and Persi Diaconis, Estimating and understanding exponential random graph models, Ann. Statist. 41 (2013), no. 5, 2428-2461. MR 3127871, https://doi.org/10.1214/13-AOS1155
  • [20] 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, https://doi.org/10.1016/j.ejc.2011.03.014
  • [21] B. DeMarco and J. Kahn, Upper tails for triangles, Random Structures Algorithms 40 (2012), no. 4, 452-459. MR 2925307, https://doi.org/10.1002/rsa.20382
  • [22] B. Demarco and J. Kahn, Tight upper tail bounds for cliques, Random Structures Algorithms 41 (2012), no. 4, 469-487. MR 2993131, https://doi.org/10.1002/rsa.20440
  • [23] Amir Dembo and Ofer Zeitouni, Large deviations techniques and applications. (Corrected reprint of the second (1998) edition), Stochastic Modelling and Applied Probability, vol. 38, Springer-Verlag, Berlin, 2010. MR 2571413
  • [24] Persi Diaconis and Svante Janson, Graph limits and exchangeable random graphs, Rend. Mat. Appl. (7) 28 (2008), no. 1, 33-61. MR 2463439
  • [25] P. Erdős and A. Rényi, A., On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (1960), 17-61. MR 0125031
  • [26] Alan Frieze and Ravi Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), no. 2, 175-220. MR 1723039, https://doi.org/10.1007/s004930050052
  • [27] 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
  • [28] 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, https://doi.org/10.1007/BF02771528
  • [29] Olav Kallenberg, Probabilistic symmetries and invariance principles, Probability and its Applications (New York), Springer, New York, 2005. MR 2161313
  • [30] R. Kenyon, C. Radin, K. Ren and L. Sadun, Multipodal Structure and Phase Transitions in Large Constrained Graphs. arXiv preprint arXiv:1405.0599, (2014).
  • [31] R. Kenyon M. Yin, On the asymptotics of constrained exponential random graphs. arXiv preprint arXiv:1406.3662, 2014.
  • [32] Yuri Kifer, Nonconventional limit theorems, Probab. Theory Related Fields, 148 (2010), no. 1-2, 71-106. MR 2653222, https://doi.org/10.1007/s00440-009-0223-9
  • [33] 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, https://doi.org/10.1214/12-AOP796
  • [34] Yuri Kifer and S. R. S. Varadhan, Nonconventional large deviations theorems, Probab. Theory Related Fields 158 (2014), no. 1-2, 197-224. MR 3152784, https://doi.org/10.1007/s00440-013-0481-4
  • [35] Jeong Han Kim and Van H. Vu, Concentration of multivariate polynomials and its applications, Combinatorica 20 (2000), no. 3, 417-434. MR 1774845, https://doi.org/10.1007/s004930070014
  • [36] 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, https://doi.org/10.1002/rsa.10113
  • [37] Rafał Latała, Estimation of moments of sums of independent real random variables, Ann. Probab. 25 (1997), no. 3, 1502-1513. MR 1457628, https://doi.org/10.1214/aop/1024404522
  • [38] László Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. MR 3012035
  • [39] 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, https://doi.org/10.1016/j.jctb.2006.05.002
  • [40] 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.
  • [41] 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, https://doi.org/10.1002/rsa.20536
  • [42] Charles Radin, Kui Ren, and Lorenzo Sadun, The asymptotics of large constrained graphs, J. Phys. A 47 (2014), no. 17, 175001, 20. MR 3197554, https://doi.org/10.1088/1751-8113/47/17/175001
  • [43] Charles Radin and Lorenzo Sadun, Phase transitions in a complex network, J. Phys. A 46 (2013), no. 30, 305002, 12. MR 3083277, https://doi.org/10.1088/1751-8113/46/30/305002
  • [44] 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, https://doi.org/10.1007/s10955-014-1151-3
  • [45] Charles Radin and Mei Yin, Phase transitions in exponential random graphs, Ann. Appl. Probab. 23 (2013), no. 6, 2458-2471. MR 3127941, https://doi.org/10.1214/12-AAP907
  • [46] Cosma Rohilla Shalizi and Alessandro Rinaldo, Consistency under sampling of exponential random graph models, Ann. Statist. 41 (2013), no. 2, 508-535. MR 3099112, https://doi.org/10.1214/12-AOS1044
  • [47] 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
  • [48] Michel Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Inst. Hautes Études Sci. Publ. Math. 81 (1995), 73-205. MR 1361756
  • [49] Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012
  • [50] 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, https://doi.org/10.1002/rsa.10032
  • [51] Mei Yin, Critical phenomena in exponential random graphs, J. Stat. Phys. 153 (2013), no. 6, 1008-1021. MR 3131507, https://doi.org/10.1007/s10955-013-0874-x
  • [52] Y. Zhao, On the lower tail variational problem for random graphs. arXiv preprint arXiv:1502.00867, 2015.

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 60F10, 05C80, 60C05, 05A20

Retrieve articles in all journals with MSC (2010): 60F10, 05C80, 60C05, 05A20


Additional Information

Sourav Chatterjee
Affiliation: Department of Statistics, Stanford University
Email: souravc@stanford.edu

DOI: https://doi.org/10.1090/bull/1539
Received by editor(s): April 22, 2016
Published electronically: June 24, 2016
Additional Notes: The author’s research was partially supported by NSF grant DMS-1441513
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society