Article ID Journal Published Year Pages File Type
420431 Discrete Applied Mathematics 2010 10 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,