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.

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

Table of n, a(n) for n=1..8.

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

Cf. A373776, A373777.

Sequence in context: A307728 A263199 A052483 * A308116 A308123 A308089

Adjacent sequences: A373772 A373773 A373774 * A373776 A373777 A373778

Keyword

nonn,more

Author

Pontus von Brömssen, Jun 18 2024

Status

approved