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:
“A man who is a politician at forty is a statesman at three score and ten. It is at this age, when he would be too old to be a clerk or a gardener or a police-court magistrate, that he is ripe to govern a country.”
—W. Somerset Maugham (1874–1965)
“There is a small steam engine in his brain which not only sets the cerebral mass in motion, but keeps the owner in hot water.”
—Unknown. New York Weekly Mirror (July 5, 1845)