When are small subgraphs of a random graph normally distributed? (Q1092512)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | When are small subgraphs of a random graph normally distributed? |
scientific article |
Statements
When are small subgraphs of a random graph normally distributed? (English)
0 references
1988
0 references
Let G be a graph and let \(X_ n\) count copies of G in a random graph K(n,p). The random variable \((X_ n-E(X_ n))/\sqrt{Var(X_ n)}\) is asymptotically normally distributed if and only if \(np^ m\to \infty\) and \(n^ 2(1-p)\to \infty\), where \(m=\max \{e(H)/| H| :\) \(H\subset G\}.\) In addition to, and in connection with this main result we investigate the formula for \(Var(X_ n)\) and the Poisson convergence of \(X_ n\).
0 references
random graph
0 references
asymptotically normally distributed
0 references
Poisson convergence
0 references