Geodesic
Note on normal approximation for number of triangles in heterogeneous Erdős-Rényi graph
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 914-926 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We obtain a bound for the convergence rate in the central limit theorem for the number of triangles in a heterogeneous Erdős-Rényi graphs. Our approach is reminiscent of Hoeffding decomposition (a common technique in the theory of U-statistics). We show that the centered and normalized number of triangles asymptotically behaves as the normalized sum of centered independent random variables when the number of vertices increases. The proposed method is simple and intuitive.
Keywords: Erdős-Rényi random graphs, central limit theorem, large deviations principle. 
@article{SEMR_2024_21_2_a18,
     author = {A. V. Logachov and A. A. Mogulskii and A. A. Yambartsev},
     title = {Note on normal approximation for number of triangles in heterogeneous {Erd\H{o}s-R\'enyi} graph},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {914--926},
     year = {2024},
     volume = {21},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a18/}
}
TY  - JOUR
AU  - A. V. Logachov
AU  - A. A. Mogulskii
AU  - A. A. Yambartsev
TI  - Note on normal approximation for number of triangles in heterogeneous Erdős-Rényi graph
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 914
EP  - 926
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a18/
LA  - en
ID  - SEMR_2024_21_2_a18
ER  - 
%0 Journal Article
%A A. V. Logachov
%A A. A. Mogulskii
%A A. A. Yambartsev
%T Note on normal approximation for number of triangles in heterogeneous Erdős-Rényi graph
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 914-926
%V 21
%N 2
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a18/
%G en
%F SEMR_2024_21_2_a18
A. V. Logachov; A. A. Mogulskii; A. A. Yambartsev. Note on normal approximation for number of triangles in heterogeneous Erdős-Rényi graph. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 2, pp. 914-926. http://geodesic.mathdoc.fr/item/SEMR_2024_21_2_a18/

[1] J. Gilmer, S. Kopparty, “A local central limit theorem for triangles in a random graph”, Random Struct. Algorithms, 48:4 (2016), 732–750 | DOI | MR | Zbl

[2] C. Lee, D.J. Wilkinson, “A review of stochastic block models and extensions for graph clustering”, Appl. Netw. Sci., 4 (2019), 122 | DOI | MR

[3] B. Bollobàs, S. Janson, O. Riordan, “The phase transition in inhomogeneous random graphs”, Random Struct. Algorithms, 31:1 (2007), 3–122 | DOI | MR | Zbl

[4] A. Ruciński, When are small subgraphs of a random graph normally distributed?, Probab. Theory Relat. Fields, 78:1 (1988), 1–10 | DOI | MR | Zbl

[5] A. Sah, M. Sawhney, “Local limit theorems for subgraph counts”, J. Lond. Math. Soc., II. Ser., 105:2 (2022), 950–1011 | DOI | MR | Zbl

[6] V.V. Petrov, Sum of independent random variables, Springer, Berlin etc., 1975 | DOI | MR | Zbl

[7] A. Dembo, O. Zeitouni, Large deviations techniques and applications, Springer, New York, 1998 | DOI | MR | Zbl

[8] K. Nowicki, J.C. Wierman, “Subgraph counts in random graphs using incomplete U-statistics methods”, Discrete Math., 72:1-3 (1988), 299–310 | DOI | MR | Zbl

[9] C. Goldschmidt, S. Griffiths, A. Scott, “Moderate deviations of subgraph counts in the Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$”, Trans. Am. Math. Soc., 373:8 (2020), 5517–5585 | DOI | MR | Zbl

[10] S. Chatterjee, S.R.S. Varadhan, “The large deviation principle for the Erdős-Rényi random graph”, Eur. J. Comb., 32:7 (2011), 1000–1017 | DOI | MR | Zbl

[11] A.V. Logachov, A.A. Mogulskii, “Exponential Chebyshev inequalities for random graphons and their applications”, Sib. Math. J., 61:4 (2020), 697–714 | DOI | MR | Zbl

[12] A.A. Bystrov, N.V. Volod'ko, “Exponential inequalities for the distribution of the number of cycles in the Erdős-Rényi random graphs”, Sib. Adv. Math., 32:2 (2022), 87–93 | DOI | MR | Zbl

[13] A.A. Bystrov, N.V. Volodko, “Exponential inequalities for the number of subgraphs in the Erdős-Rényi random graph”, Stat. Probab. Lett., 195 (2023), 109763 | DOI | MR | Zbl

[14] A.A. Bystrov, N.V. Volodko, “Exponential inequalities for the tail probabilities of the number of cycles in generalized random graphs”, Sib. Adv. Math., 33:3 (2023), 181–189 | DOI | MR

[15] P. Eichelsbacher, B. Rednoß, “Kolmogorov bounds for decomposable random variables and subgraph counting by the Stein-Tikhomirov method”, Bernoulli, 29:3 (2023), 1821–1848 | DOI | MR | Zbl

[16] N. Privault, G. Serafin, “Normal approximation for sums of weighted U-statistics-application to Kolmogorov bounds in random subgraph counting”, Bernoulli, 26:1 (2020), 587–615 | DOI | MR | Zbl

[17] Z.-S. Zhang, “Berry-Esseen bounds for generalized U-statistics”, Electron. J. Probab., 27 (2022), 134 | DOI | MR | Zbl

[18] W. Hoeffding, “A class of statistics with asymptotically normal distribution”, Breakthroughs in statistics, eds. Kotz S., Johnson N.L., Springer, New York, 1992, 308–334 | DOI