login
A373775
For an oriented graph D, let X_m(D) be the number of copies of D in a random tournament (i.e., a complete graph, each of whose edges is directed randomly with probability 1/2 for each direction) on m vertices. The variance of X_m(D) is a polynomial in m, and a(n) is the minimum degree of this polynomial over all weakly connected oriented graphs D on n vertices. a(n) = 0 if the variance of X_m(D) is identically 0 for some such D.
2
0, 0, 3, 0, 5, 6, 9, 0
OFFSET
1,3
COMMENTS
For any D with n vertices, Var(X_m(D)) is either identically zero or a polynomial in m of degree between n and 2*n-3.
It follows from Theorem 6 in Andersson (1998) that a(n) = 0 if and only if n is a power of 2.
The expected value of X_m(D) equals m!/((m-n)!*2^e*aut(D)), where e is the number of edges of D and aut(D) is the number of automorphisms of D.
If D and D' are the reverses of each other, i.e., D' is obtained from D by reversing the direction of all its edges, X_m(D) and X_m(D') are equidistributed.
LINKS
Pontus Andersson (von Brömssen), On the asymptotic distributions of subgraph counts in a random tournament, Random Structures & Algorithms 13 (1998), 249-260.
Pontus Andersson (von Brömssen), Small variance of subgraph counts in a random tournament, Statistics & Probability Letters 49 (2000), 135-138.
CROSSREFS
Sequence in context: A307728 A263199 A052483 * A308116 A308123 A308089
KEYWORD
nonn,more
AUTHOR
STATUS
approved