Variance of the subgraph count for sparse Erdos-Renyi graphs
Robert Ellis
Department of Applied Mathematics
Illinois Institute of Technology
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'* isomorphic 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. This is joint work with James P. Ferry.