Variance of the subgraph count for sparse Erd?sRnyi graphs
We develop formulas for the variance of the number of copies of a small subgraph H H in the Erd?sRnyi 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 H H . 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 H H is connected with non-null 2-core, or when H 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 H is a cycle with attached trees and when H H is a tree.
variance erd?srnyi graph small subgraph subgraph plot graph isomorphism