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

详细信息    查看全文

• 作者：Robert B. Ellis ; James P. Ferry
• 关键词：Erd&#x151 ; s– ; Ré ; nyi graph ; Small subgraph ; Variance ; Subgraph plot ; Graph isomorphism
• 刊名：Discrete Applied Mathematics
• 出版年：2010
• 出版时间：28 March 2010
• 年：2010
• 卷：158
• 期：6
• 页码：649-658
• 全文大小：675 K

文摘

We develop formulas for the variance of the number of copies of a small subgraph H 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 overlapping 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 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.