Tournament (graph Theory) - Score Sequences and Score Sets

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:

    “Gargantua, at the age of four hundred four score and forty- four years begat his son Pantagruel, from his wife, named Badebec, daughter of the King of the Amaurotes in Utopia, who died in child-birth: because he was marvelously huge and so heavy that he could not come to light without suffocating his mother.”
    —François Rabelais (1494–1553)

    “Certain anthropologists hold that man, having discovered tools, ceased to evolve biologically. Animals, never having discovered them, continue to fashion drills out of their beaks, oars out of their hind feet, wings out of their forefeet, suits of armor out of their hides, levers out of their horns, saws out of their teeth. Whether this be true or not, all authorities agree that man is the tool-using animal. It sets him off from the rest of the animal kingdom as drastically as does speech.”
    —Stuart Chase (1888–1985)