An Independent Process Approximation to Sparse Random Graphs with a Prescribed Number of Edges and Triangles

Abstract

We prove a $pre$-$asymptotic$ bound on the total variation distance between the uniform distribution over two types of undirected graphs with $n$ nodes. One distribution places a prescribed number of $k_T$ triangles and $k_S$ edges not involved in a triangle independently and uniformly over all possibilities, and the other is the uniform distribution over simple graphs with exactly $k_T$ triangles and $k_S$ edges not involved in a triangle. As a corollary, for $k_S=o(n)$ and $k_T=o(n)$ as $n$ tends to infinity, the total variation distance tends to $0$, at a rate that is given explicitly. Our main tool is Chen-Stein Poisson approximation, hence our bounds are explicit for all finite values of the parameters.

14 Pages

References in corpus (2)

• Random graphs with clustering
• On the absolute constants in the Berry-Esseen type inequalities for identically distributed summands