A large deviation principle for the Erdős-Rényi uniform random graph. (English) Zbl 1398.05179

Summary: Starting with the large deviation principle (LDP) for the Erdős-Rényi binomial random graph \(\mathcal{G}(n,p)\) (edge indicators are i.i.d.), due to S. Chatterjee and S. R. S. Varadhan [Eur. J. Comb. 32, No. 7, 1000–1017 (2011; Zbl 1230.05259)], we derive the LDP for the uniform random graph \(\mathcal{G}(n,m)\) (the uniform distribution over graphs with \(n\) vertices and \(m\) edges), at suitable \(m=m_n\). Applying the latter LDP we find that tail decays for subgraph counts in \(\mathcal{G}(n,m_n)\) are controlled by variational problems, which up to a constant shift, coincide with those studied by R. Kenyon et al. [“Bipodal structure in oversaturated random graphs”, Int. Math. Res. Not. 2018, No. 4, 1009–1044 (2018)] and C. Radin and L. Sadun [J. Phys. A, Math. Theor. 46, No. 30, Article ID 305002, 12 p. (2013; Zbl 1314.82011)] in the context of constrained random graphs, e.g., the edge/triangle model.


05C80 Random graphs (graph-theoretic aspects)
60F10 Large deviations
Full Text: DOI arXiv Euclid


[1] N. Alon and J. H. Spencer, The probabilistic method, fourth ed., Wiley Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2016. · Zbl 1333.05001
[2] F. Augeri, Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdös-Renyi graphs, preprint, arXiv:1809.11148.
[3] B. B. Bhattacharya, S. Ganguly, E. Lubetzky, and Y. Zhao, Upper tails and independence polynomials in random graphs, Adv. Math. 319 (2017), 313–347. · Zbl 1370.05099
[4] 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. · Zbl 1213.05161
[5] S. Chatterjee and A. Dembo, Nonlinear large deviations, Adv. Math. 299 (2016), 396–450. · Zbl 1356.60045
[6] S. 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. · Zbl 1230.05259
[7] N. Cook and A. Dembo, Large deviations of subgraph counts for sparse Erdős–Rényi graphs, preprint, arXiv:1809.11148.
[8] A. Dembo and O. Zeitouni, Large deviations techniques and applications, Stochastic Modelling and Applied Probability, vol. 38, Springer-Verlag, Berlin, 2010. · Zbl 1177.60035
[9] F. den Hollander, M. Mandjes, A. Roccaverde, and N. J. Starreveld, Ensemble equivalence for dense graphs, Electron. J. Probab. 23 (2018), Paper No. 12, 26 pp. · Zbl 1387.05240
[10] R. Eldan, Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations, Geom. Funct. Anal., to appear. · Zbl 1428.60045
[11] W. Hoeffding, On the distribution of the number of successes in independent trials, Ann. Math. Statist. 27 (1956), 713–721. · Zbl 0073.13902 · doi:10.1214/aoms/1177728178
[12] S. Janson, T. Łuczak, and A. Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. · Zbl 0968.05003
[13] R. Kenyon, C. Radin, K. Ren, and L. Sadun, Multipodal structure and phase transitions in large constrained graphs, J. Stat. Phys. 168 (2017), no. 2, 233–258. · Zbl 1376.82029
[14] R. Kenyon, C. Radin, K. Ren, and L. Sadun, The phases of large networks with edge and triangle constraints, J. Phys. A 50 (2017), no. 43, 435001, 22. · Zbl 1386.82015
[15] R. Kenyon, C. Radin, K. Ren, and L. Sadun, Bipodal structure in oversaturated random graphs, Int. Math. Res. Not. (IMRN) 2018 (2018), no. 4, 1009–1044. · Zbl 1404.05196
[16] L. Lovász, Large networks and graph limits, American Mathematical Society Colloquium Publications, vol. 60, American Mathematical Society, Providence, RI, 2012. · Zbl 1292.05001
[17] L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), no. 6, 933–957. · Zbl 1113.05092
[18] E. Lubetzky and Y. Zhao, On replica symmetry of large deviations in random graphs, Random Structures Algorithms 47 (2015), no. 1, 109–146. · Zbl 1348.05195
[19] E. Lubetzky and Y. Zhao, On the variational problem for upper tails in sparse random graphs, Random Structures Algorithms 50 (2017), no. 3, 420–436. · Zbl 1364.05063
[20] C. Radin and L. Sadun, Phase transitions in a complex network, J. Phys. A 46 (2013), no. 30, 305002, 12. · Zbl 1314.82011
[21] Y. Zhao, On the lower tail variational problem for random graphs, Combin. Probab. Comput. 26 (2017), no. 2, 301–320. · Zbl 1371.05274 · doi:10.1017/S0963548316000262
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.