A373776 - OEIS

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.

%I #11 Jun 23 2024 11:51:20

%S 0,0,1,0,9,1,479,0

%N 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.

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

%H Pontus Andersson (von Brömssen), <a href="https://doi.org/10.1002/(SICI)1098-2418(199810/12)13:3/4%3C249::AID-RSA4%3E3.0.CO;2-V">On the asymptotic distributions of subgraph counts in a random tournament</a>, Random Structures & Algorithms 13 (1998), 249-260.

%e For 1 <= n <= 8, the following n-vertex graphs give the minimum limit of Var(X_m(D))/m^A373775(n):

%e 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.

%e 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.

%e n = 4: When D is the path 1 -> 2 -> 3 <- 4 (or its reverse), Var(X_m(D)) = 0; a(4) = 0.

%e 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.

%e 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.

%e 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.

%e 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.

%Y Cf. A373775, A373777 (denominators).

%K nonn,frac,more

%O 1,5

%A _Pontus von Brömssen_, Jun 18 2024