25.3. 25.3 Existence of -tournaments with prescribed score sequence

The simplest supertournament is the classical tournament, in our notation the -tournament.

Now, we give the characterization of score sequences of tournaments which is due to Landau [ 159 ]. This result has attracted quite a bit of attention as nearly a dozen different proofs appear in the literature. Early proofs tested the readers patience with special choices of subscripts, but eventually such gymnastics were replaced by more elegant arguments. Many of the existing proofs are discussed in a survey written by K. Brooks Reid [ 236 ]. The proof we give here is due to Thomassen [ 270 ]. Further, two new proofs can be found in the paper due to Griggs and Reid [ 95 ].

Theorem 25.1 (Landau [ 159 ]) A sequence of nonnegative integers is the score vector of a -tournament if and only if for each subset

with equality, when .

This theorem, called Landau theorem is a nice necessary and sufficient condition, but its direct application can require the test of exponential number of subsets.

If instead of the nonordered vector we consider a nondecreasingly ordered sequence , then due to the monotonity the inequalities (25.2), called Landau inequalities, we get the following consequence.

Corollary 25.2 (Landau [ 159 ]) A nondecreasing sequence of nonnegative integers is the score sequence of some -tournament, if and only if

for , with equality for .

Proof. Necessity If a nondecreasing sequence of nonnegative integers is the score sequence of an -tournament , then the sum of the first scores in the sequence counts exactly once each arc in the subtournament induced by plus each arc from to . Therefore the sum is at least , the number of arcs in . Also, since the sum of the scores of the vertices counts each arc of the tournament exactly once, the sum of the scores is the total number of arcs, that is, .

Sufficiency (Thomassen [ 270 ]) Let be the smallest integer for which there is a nondecreasing sequence of nonnegative integers satisfying Landau's conditions (25.3), but for which there is no -tournament with score sequence . Among all such , pick one for which is as lexicografically small as possible.

First consider the case where for some ,

By the minimality of , the sequence is the score sequence of some tournament . Further,

for each , with the equality when . Therefore, by the minimality of , the sequence is the score sequence of some tournament . By forming the disjoint union of and and adding all arcs from to , we obtain a tournament with score sequence .

Now, consider the case where each inequality in (25.3) is strict when (in particular ). Then the sequence satisfies (25.3) and by the minimality of , is the score sequence of some tournament . Let and be the vertices with scores and respectively. Since the score of is larger than that of , then according to Lemma 25.5 has a path from to of length . By reversing the arcs of , we obtain a tournament with score sequence , a contradiction.

Landau's theorem is the tournament analog of the Erdős-Gallai theorem for graphical sequences [ 71 ]. A tournament analog of the Havel-Hakimi theorem [ 102 ], [ 109 ] for graphical sequences is the following result.

Theorem 25.3 (Reid, Beineke [ 238 ]) A nondecreasing sequence of nonnegative integers, , is the score sequence of an -tournament if and only if the new sequence

arranged in nondecreasing order, is the score sequence of some -tournament.

Proof. See [ 238 ].