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:
“Earthly minds, like mud walls, resist the strongest batteries: and though, perhaps, sometimes the force of a clear argument may make some impression, yet they nevertheless stand firm, and keep out the enemy, truth, that would captivate or disturb them. Tell a man passionately in love, that he is jilted; bring a score of witnesses of the falsehood of his mistress, it is ten to one but three kind words of hers shall invalidate all their testimonies.”
—John Locke (1632–1704)
“In my dealing with my child, my Latin and Greek, my accomplishments and my money stead me nothing; but as much soul as I have avails. If I am wilful, he sets his will against mine, one for one, and leaves me, if I please, the degradation of beating him by my superiority of strength. But if I renounce my will, and act for the soul, setting that up as umpire between us two, out of his young eyes looks the same soul; he reveres and loves with me.”
—Ralph Waldo Emerson (1803–1882)