KOLMOGOROV BOUNDS FOR THE NORMAL APPROXIMATION OF THE NUMBER OF TRIANGLES IN THE ERDS-RENYI RANDOM GRAPH

We bound the error for the normal approximation of the number of triangles in the Erdos-Renyi random graph with respect to the Kolmogorov metric. Our bounds match the best available Wasserstein bounds obtained by Barbour et al. [(1989). A central limit theorem for decomposable random variables with applications to random graphs. Journal of Combinatorial Theory, Series B 47: 125-145], resolving a long-standing open problem. The proofs are based on a new variant of the Stein-Tikhomirov method-a combination of Stein's method and characteristic functions introduced by Tikhomirov [(1976). The rate of convergence in the central limit theorem for weakly dependent variables. Vestnik Leningradskogo Universiteta 158-159, 166].

Automated summary

In this study, we bound the error in the normal approximation of the number of triangles in the Erdos-Renyi random graph with respect to the Kolmogorov metric. Our bounds match the best available Wasserstein bounds obtained by Barbour et al., resolving a long-standing open problem. The proofs are based on a new variant of the Stein-Tikhomirov method, which combines Stein's method and characteristic functions introduced by Tikhomirov.