= Landau's theorem on tournament scores
{c}
= Landau's characterization
{c}
{synonym}
A nondecreasing list of <nonnegative integers> $s_1\le\cdots\le s_n$ is the list of <outdegrees> of a <tournament> exactly when
$$
\sum_{i=1}^k s_i\ge\binom{k}{2}\quad(1\le k<n),\qquad \sum_{i=1}^ns_i=\binom n2.
$$
Necessity follows because any $k$ vertices have $\binom{k}{2}$ internal edges, each contributing one to their total <outdegree>. Sufficiency is the substantive part of <Landau's theorem on tournament scores>.
The list $(1,1,1)$ is realized by a directed triangle; $(0,1,2)$ is realized by a <transitive tournament>. The list $(0,0,3,3)$ has the correct total but fails the inequality at $k=2$, so it cannot occur. Total score alone therefore does not characterize a tournament.
Back to article page
