Variance of the subgraph count for sparse Erdős–Rényi graphs

We develop formulas for the variance of the number of copies of a small subgraph HH in the Erdős–Rényi 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˜≅H overlapping HH. In the sparse case, building on previous results of Janson, Łuczak, and Rucinski allows restriction of the polynomial to the asymptotically contributing portion either when HH is connected with non-null 2-core, or when HH 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 HH is a cycle with attached trees and when HH is a tree.