Sciact
  • EN
  • RU

Note on normal approximation for number of triangles in heterogeneous Erdős-Rényi graph Full article

Journal Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304
Output data Year: 2024, Volume: 21, Number: 2, Pages: 913-926 Pages count : 14 DOI: 10.33048/semi.2024.21.060
Tags Erdos-Renyi random graphs, central limit theorem, large deviations principle.
Authors Logachov A.V. 1,2 , Mogulskii A.A. 1 , Yambartsev A.A. 3
Affiliations
1 Lab. of Probability Theory and Math. Statistics, Sobolev Institute of Mathematics
2 Dep. of Computer Science in Economics, Novosibirsk State Technical University
3 Institute of Mathematics and Statistics, University of Sao Paulo

Funding (2)

1 Sobolev Institute of Mathematics FWNF-2022-0010
2 Министерство науки и высшего образования РФ
Mathematical Center in Akademgorodok 		075-15-2019-1613, 075-15-2022-281

Abstract: We obtain a bound for the convergence rate in the central limit theorem for the number of triangles in a heterogeneous Erdos-Renyi 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.
Cite: Logachov A.V. , Mogulskii A.A. , Yambartsev A.A.
Note on normal approximation for number of triangles in heterogeneous Erdős-Rényi graph
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. V.21. N2. P.913-926. DOI: 10.33048/semi.2024.21.060 WOS Scopus
Dates:
Submitted: Mar 7, 2024
Published print: Nov 1, 2024
Published online: Nov 1, 2024
Identifiers:
Web of science: WOS:001396421100002
Scopus: 2-s2.0-85212349816
Citing: Пока нет цитирований
Altmetrics: