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 is a score sequence if and only if :
Let be the number of different score sequences of size . The sequence (sequence A000571 in OEIS) 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:
where Takács later showed, using some reasonable but unproven assumptions, that
where
Together these provide evidence that:
Here signifies an asymptotically tight bound.
Yao showed that every nonempty set of nonnegative integers is the score set for some tournament.
Read more about this topic: Tournament (graph Theory)
Famous quotes containing the words score and/or sets:
“Whereas, before, our forefathers had no other books but the score and the tally, thou hast caused printing to be used, and, contrary to the King, his crown, and dignity, thou hast built a paper-mill.”
—William Shakespeare (1564–1616)
“It is mediocrity which makes laws and sets mantraps and spring-guns in the realm of free song, saying thus far shalt thou go and no further.”
—James Russell Lowell (1819–91)