HP Labs Technical Reports

Compound Poisson Approximations of Subgraph Counts in Random Graphs

Stark, Dudley

HPL-BRIMS-98-22

Keyword(s):Poisson approximation; random graphs; Stein's method

Abstract:Poisson approximations for the counts of a given subgraph in large random graphs were accomplished using Stein's method by Barbour and others. Compound Poisson approximation results, on the other hand, have not appeared, at least partly because of the lack of a suitable coupling. We address that problem by introducing the concept of cluster determining pairs, leading to a useful coupling for a large class of subgraphs we call local. We find bounds on the compound Poisson approximation of counts of local subgraphs in large random graphs.

16 Pages

Back to Index