A373776 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. a(n) is the numerator of the minimum limit, as m tends to infinity, of Var(X_m(D))/m^A373775(n) over all weakly connected oriented graphs D on n vertices.

0, 0, 1, 0, 9, 1, 479, 0

Offset

1,5

Comments

It follows from Theorem 6 in Andersson (1998) that a(n) = 0 if and only if n is a power of 2.

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.

Example

For 1 <= n <= 8, the following n-vertex graphs give the minimum limit of Var(X_m(D))/m^A373775(n):
n <= 2: The number of vertices and the number of edges in a tournament are independent of the directions of the edges in the tournament, so Var(X_m(D)) = 0 when D is a single vertex or a single edge; a(1) = a(2) = 0.
n = 3: When D is any of the 5 weakly connected oriented graphs, except the directed path 1 -> 2 -> 3, Var(X_m(D)) = (1/32) * m * (m-1) * (m-2); a(3) = 1.
n = 4: When D is the path 1 -> 2 -> 3 <- 4 (or its reverse), Var(X_m(D)) = 0; a(4) = 0.
n = 5: When D is the digraph (or its reverse) given by "&DIKCQ?" in digraph6 format, Var(X_m(D)) = (9/2048) * m * (m-1) * (m-2) * (m-3) * (m-4); a(5) = 9.
n = 6. When D is the digraph (or its reverse) given by "&EDA??HC" in digraph6 format, Var(X_m(D)) = (1/256) * m * (m-1) * (m-2) * (m-3) * (m-4) * (m-5); a(6) = 1.
n = 7: When D is the digraph (or its reverse) given by "&FDa?w]C_R?" in digraph6 format, Var(X_m(D)) = (1/2147483648) * (479*m^2+3847*m-11960) * m * (m-1) * (m-2) * (m-3) * (m-4) * (m-5) * (m-6); a(7) = 479.
n = 8: When D is any of the digraphs obtained from two copies of the path 1 -> 2 -> 3 <- 4 by joining the two copies of one of the vertices by an edge, or the reverse of one of these graphs (8 graphs in total), Var(X_m(D)) = 0; a(8) = 0.

Crossrefs

Cf. A373775, A373777 (denominators).

Sequence in context: A051231 A258437 A046761 * A352688 A335539 A193373

Adjacent sequences: A373773 A373774 A373775 * A373777 A373778 A373779

Keyword

nonn,frac,more

Author

Pontus von Brömssen, Jun 18 2024

Status

approved