The Asymptotic Number of Score Sequences

A tournament on a graph is an orientation of its edges. The score sequence lists the in-degrees in non-decreasing order. Works by Winston and Kleitman (J Comb Theory Ser A 35(2):208–230, 1983) and Kim and Pittel (J Comb Theory Ser A 92(2):197–206, 2000) showed that the number Sₙ S n of score sequences on the complete graph Kₙ K n satisfies Sₙ=Θ (4ⁿ/n5/2) S n = Θ ( 4 n / n 5 / 2 ) . By combining a recent recurrence relation for Sₙ S n in terms of the Erdős–Ginzburg–Ziv numbers Nₙ N n with the limit theory for discrete infinitely divisible distributions, we observe that n5/2Sₙ/4ⁿ→ e^λ /2√π n 5 / 2 S n / 4 n → e λ / 2 π , where λ =∑ ₖ₌₁^∞ Nₖ/k4ᵏ λ = ∑ k = 1 ∞ N k / k 4 k . This limit agrees numerically with the asymptotics of Sₙ S n conjectured by Takács (J Stat Plan Inference 14(1):123–142, 1986). We also identify the asymptotic number of strong score sequences, and show that the number of irreducible subscores in a random score sequence converges in distribution to a shifted negative binomial with parameters $$r=2$$ r = 2 and p=e-λ p = e - λ .