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
    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
    0 references
    random graph
    0 references
    asymptotically normally distributed
    0 references
    Poisson convergence
    0 references