Kolmogorov bounds for the normal approximation of the number of\n triangles in the Erdos-Renyi random graph

2017/04/02 by Adrian Röllin, Röllin, Adrian
Computer Science · Mathematics · #60F05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1704.00410

openalex publication_date 2017/04/02 · openalex created_date 2022/08/05 · openalex updated_date 2026/07/28

Abstract

We bound the error for the normal approximation of the number of triangles in\nthe Erdos-Renyi random graph with respect to the Kolmogorov metric. Our bounds\nmatch the best available Wasserstein-bounds obtained by Barbour, Karonski and\nRucinski (1989), resolving a long-standing open problem. The proofs are based\non a new variant of the Stein-Tikhomirov method - a combination of Stein's\nmethod and characteristic functions introduced by Tikhomirov (1980).\n

Related

• Normal approximation for sums of discrete U-statistics - application to Kolmogorov bounds in random subgraph counting
• Kolmogorov bounds for decomposable random variables and subgraph counting by the Stein-Tikhomirov method
• Normal approximation for generalized U-statistics and weighted random\n graphs
• A local central limit theorem for the number of triangles in a random graph
• Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph G(n,m): The Lower Tail