A373775 - OEIS

%I #7 Jun 23 2024 11:51:24

%S 0,0,3,0,5,6,9,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. 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.

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

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

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

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

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

%H Pontus Andersson (von Brömssen), <a href="https://doi.org/10.1016/S0167-7152(00)00041-9">Small variance of subgraph counts in a random tournament</a>, Statistics & Probability Letters 49 (2000), 135-138.

%Y Cf. A373776, A373777.

%K nonn,more

%O 1,3

%A _Pontus von Brömssen_, Jun 18 2024