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)
“And weren’t there special cemetery flowers,
That, once grief sets to growing, grief may rest:
The flowers will go on with grief awhile,
And no one seem neglecting or neglected?
A prudent grief will not despise such aids.”
—Robert Frost (1874–1963)