Variance of the subgraph count for sparse Erdos-Renyi graphs

We develop formulas for the variance of the number of copies of a small subgraph H in the Erdos-Renyi random graph. The central technique employs a graph overlay polynomial encoding subgraph symmetries, which is of independent interest, that counts the number of copies (H) over tilde congruent to H overlapping H. In the sparse case, building on previous results of Janson, Luczak, and Rucinski allows restriction of the polynomial to the asymptotically contributing portion either when H is connected with non-null 2-core, or when H is a tree. In either case we give a compact computational formula for the asymptotic variance in terms of a rooted tree overlay polynomial. Two cases for which the formula is valid in a range for which both the expected value and variance are finite are when H is a cycle with attached trees and when H is a tree. (C) 2009 Elsevier B.V. All rights reserved.