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:
“How many miles to Babylon?
Three score and ten.
Can I get there by candlelight?
Yes, and back again.”
—Mother Goose (fl. 17th–18th century. How many miles to Babylon? (l. 1–4)
“Drink, sir, is a great provoker of three things ... nose-painting, sleep, and urine. Lechery, sir, it provokes and unprovokes: it provokes the desire but it takes away the performance. Therefore much drink may be said to be an equivocator with lechery: it makes him and it mars him; it sets him on and it takes him off.”
—William Shakespeare (1564–1616)