Editing Tournament (graph theory) (section)

==Score sequences and score sets==
The score sequence of a tournament is the nondecreasing sequence of outdegrees of the vertices of a tournament.  The score set of a tournament is the set of integers that are the outdegrees of vertices in that tournament.

'''Landau's Theorem (1953)''' A nondecreasing sequence of integers <math>(s_1, s_2, \ldots, s_n)</math> is a score sequence if and only if:{{sfnp|Landau|1953}}
# <math>0 \le s_1 \le s_2 \le \cdots \le s_n</math>
# <math>s_1 + s_2 + \cdots + s_i \ge {i \choose 2}, \text{ for }i = 1, 2, \ldots, n - 1</math>
# <math>s_1 + s_2 + \cdots + s_n = {n \choose 2}.</math>

Let <math>s(n)</math> be the number of different score sequences of size <math>n</math>. The sequence <math>s(n)</math> {{OEIS|id=A000571}} starts as:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

Winston and Kleitman proved that for sufficiently large ''n'':
:<math>s(n) > c_1 4^n n^{-5/2},</math>
where <math>c_1 = 0.049.</math>
Takács later showed, using some reasonable but unproven assumptions, that
:<math>s(n) < c_2 4^n n^{-5/2},</math>
where <math>c_2 < 4.858.</math>{{sfnp|Takács|1991}}

Together these provide evidence that:
:<math>s(n) \in \Theta (4^n n^{-5/2}).</math>

Here <math>\Theta</math> signifies an [[Big O notation#Related asymptotic notations|asymptotically tight bound]].

Yao showed that every nonempty set of nonnegative integers is the score set for some tournament.{{sfnp|Yao|1989}}