Subgraph counts in random graphs using incomplete U-statistics methods (Q1119948)

In this paper the authors have established that the subgraph count random variable \(S_ n(G)\) has an asymptotic normal distribution for all graphs G with no isolated vertices and for a wide range of values of p including any constant p and sequences of p(n) tending to 0 or 1 sufficiently slowly. This result fills a substantial gap in the literature on asymptotic subgraph count distribuions. The authors have introduced statistical tools for treating sums of dependent random variables, from the theory of U-statistics and have adapted them skillfully for treatment of subgraph counts. They have considered counts of intersections of isomorphic subgraphs for computation of variances of the relevant statistics.