Small variance of subgraph counts in a random tournament (Q1579850)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Small variance of subgraph counts in a random tournament
scientific article

    Statements

    Small variance of subgraph counts in a random tournament (English)
    0 references
    0 references
    14 September 2000
    0 references
    If \(D\) is an oriented graph with \(v\) vertices, let \(N(T_n,D)\) denote the number of copies of \(D\) in the random tournament \(T_n\) with \(n\) labelled vertices. It is known that the variance of \(N(T_n, D)\) is a polynomial in \(n\), which, for ``most'' \(D\), is of degree \(2v-3\); see \textit{P. Andersson} [On the asymptotic distributions of subgraph counts in a random tournament, Random Struct. Algorithms 13, No. 3-4, 249-260 (1998)]. It is shown in the present paper that there are arbitrarily large oriented \(2^k\)-cycles for which this degree is as small as \(v\).
    0 references
    subgraph counts
    0 references
    random tournament
    0 references
    0 references

    Identifiers