Moderate deviations of subgraph counts in the Erdős-Rényi random graphs 𝐺(𝑛,𝑚) and 𝐺(𝑛,𝑝)

Goldschmidt, Christina; Griffiths, Simon; Scott, Alex

doi:10.1090/tran/8117

Moderate deviations of subgraph counts in the Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$
HTML articles powered by AMS MathViewer

by Christina Goldschmidt, Simon Griffiths and Alex Scott PDF

Trans. Amer. Math. Soc. 373 (2020), 5517-5585 Request permission

Abstract:

The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the Erdős-Rényi random graph $G(n,m)$. Our approach is based on applying Freedman’s inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model.

References

Kazuoki Azuma, Weighted sums of certain dependent random variables, Tohoku Math. J. (2) 19 (1967), 357–367. MR 221571, DOI 10.2748/tmj/1178243286
R. R. Bahadur, Some approximations to the binomial distribution function, Ann. Math. Statist. 31 (1960), 43–54. MR 120675, DOI 10.1214/aoms/1177705986
A. D. Barbour, MichałKaroński, and Andrzej Ruciński, A central limit theorem for decomposable random variables with applications to random graphs, J. Combin. Theory Ser. B 47 (1989), no. 2, 125–145. MR 1047781, DOI 10.1016/0095-8956(89)90014-2
Béla Bollobás, Degree sequences of random graphs, Discrete Math. 33 (1981), no. 1, 1–19. MR 597223, DOI 10.1016/0012-365X(81)90253-3
Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
Sourav Chatterjee, An introduction to large deviations for random graphs, Bull. Amer. Math. Soc. (N.S.) 53 (2016), no. 4, 617–642. MR 3544262, DOI 10.1090/bull/1539
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
Amir Dembo and Eyal Lubetzky, A large deviation principle for the Erdős-Rényi uniform random graph, Electron. Commun. Probab. 23 (2018), Paper No. 13. MR 3873786, DOI 10.1214/18-ECP181
Hanna Döring and Peter Eichelsbacher, Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices, Electron. J. Probab. 14 (2009), no. 92, 2636–2656. MR 2570014, DOI 10.1214/EJP.v14-723
Hanna Döring and Peter Eichelsbacher, Moderate deviations via cumulants, J. Theoret. Probab. 26 (2013), no. 2, 360–385. MR 3055808, DOI 10.1007/s10959-012-0437-0
Valentin Féray, Pierre-Loïc Méliot, and Ashkan Nikeghbali, Mod-$ϕ$ convergence, SpringerBriefs in Probability and Mathematical Statistics, Springer, Cham, 2016. Normality zones and precise deviations. MR 3585777, DOI 10.1007/978-3-319-46822-8
David A. Freedman, On tail probabilities for martingales, Ann. Probability 3 (1975), 100–118. MR 380971, DOI 10.1214/aop/1176996452
Svante Janson, A functional limit theorem for random graphs with applications to subgraph count statistics, Random Structures Algorithms 1 (1990), no. 1, 15–37. MR 1068489, DOI 10.1002/rsa.3240010103
Svante Janson, Orthogonal decompositions and functional limit theorems for random graph statistics, Mem. Amer. Math. Soc. 111 (1994), no. 534, vi+78. MR 1219708, DOI 10.1090/memo/0534
Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
Svante Janson and Krzysztof Nowicki, The asymptotic distributions of generalized $U$-statistics with applications to random graphs, Probab. Theory Related Fields 90 (1991), no. 3, 341–375. MR 1133371, DOI 10.1007/BF01193750
Svante Janson and Andrzej Ruciński, The infamous upper tail, Random Structures Algorithms 20 (2002), no. 3, 317–342. Probabilistic methods in combinatorial optimization. MR 1900611, DOI 10.1002/rsa.10031
Svante Janson and Lutz Warnke, The lower tail: Poisson approximation revisited, Random Structures Algorithms 48 (2016), no. 2, 219–246. MR 3449596, DOI 10.1002/rsa.20590
M. Harel, F. Mousset and W. Samotij, Upper tails via high moments and entropic stability, arXiv::1904.08212 [math.PR] (2019)
Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363, DOI 10.1080/01621459.1963.10500830
Kai Krokowski, Anselm Reichenbachs, and Christoph Thäle, Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation, Ann. Probab. 45 (2017), no. 2, 1071–1109. MR 3630293, DOI 10.1214/15-AOP1081
Pu Gao and Nicholas Wormald, Enumeration of graphs with a heavy-tailed degree sequence, Adv. Math. 287 (2016), 412–450. MR 3422681, DOI 10.1016/j.aim.2015.09.002
J. E. Littlewood, On the probability in the tail of a binomial distribution, Advances in Appl. Probability 1 (1969), 43–72. MR 240858, DOI 10.2307/1426408
Eyal Lubetzky and Yufei Zhao, On the variational problem for upper tails in sparse random graphs, Random Structures Algorithms 50 (2017), no. 3, 420–436. MR 3632418, DOI 10.1002/rsa.20658
Colin McDiarmid, Concentration, Probabilistic methods for algorithmic discrete mathematics, Algorithms Combin., vol. 16, Springer, Berlin, 1998, pp. 195–248. MR 1678578, DOI 10.1007/978-3-662-12788-9_{6}
Colin McDiarmid, On the method of bounded differences, Surveys in combinatorics, 1989 (Norwich, 1989) London Math. Soc. Lecture Note Ser., vol. 141, Cambridge Univ. Press, Cambridge, 1989, pp. 148–188. MR 1036755
Brendan D. McKay, On Littlewood’s estimate for the binomial distribution, Adv. in Appl. Probab. 21 (1989), no. 2, 475–478. MR 997736, DOI 10.2307/1427172
Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, European J. Combin. 11 (1990), no. 6, 565–580. MR 1078713, DOI 10.1016/S0195-6698(13)80042-X
Gesine Reinert and Adrian Röllin, Random subgraph counts and $U$-statistics: multivariate normal approximation via exchangeable pairs and embedding, J. Appl. Probab. 47 (2010), no. 2, 378–393. MR 2668495, DOI 10.1239/jap/1276784898
A. Röllin, Kolmogorov bounds for the Normal approximation of the number of triangles in the Erdős–Rényi random graph, arXiv:1704.00410 [math.PR] (2017).
Andrzej Ruciński, When are small subgraphs of a random graph normally distributed?, Probab. Theory Related Fields 78 (1988), no. 1, 1–10. MR 940863, DOI 10.1007/BF00718031
Van H. Vu, A large deviation result on the number of small subgraphs of a random graph, Combin. Probab. Comput. 10 (2001), no. 1, 79–94. MR 1827810, DOI 10.1017/S0963548399004095
Lutz Warnke, On the method of typical bounded differences, Combin. Probab. Comput. 25 (2016), no. 2, 269–299. MR 3455677, DOI 10.1017/S0963548315000103
Yufei Zhao, On the lower tail variational problem for random graphs, Combin. Probab. Comput. 26 (2017), no. 2, 301–320. MR 3603970, DOI 10.1017/S0963548316000262