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
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
0 references