1
$\begingroup$

There is a Landau's theorem related to tournaments theory. Looks like the sequence $(0, 1, 3, 3, 3)$ satisfies all three conditions from the theorem, but it is not possible for 5 people to play tournament in such a way (if there are no ties). Did I miss something?

  • 0
    @belisarius Yes, here is a similar question on the same forum http://math.stackexchange.com/questions/145662/sufficient-condition-for-tournament-score-sequences2012-10-21

2 Answers 2

4

Player $A$ loses to everyone.

Player $B$ beats player $A$ and loses to everyone else.

Players $C$, $D$, and $E$ beat each other cyclically, like rock-paper-scissors.

  • 0
    There is no requirement that the graph be acyclic.2012-10-21
1

Draw $K_5$, the complete graph on $5$ vertices, and assign directions to just enough edges to give one vertex ($A$ in the picture below) a score (outdegree) of $0$ and another ($B$ in the picture) a score of $1$.

enter image description here

At this point only the red edges have not been assigned orientations, and it’s clear that there are exactly two ways to orient them to gives vertices $C,D$, and $E$ scores of $3$: they must form a cycle, either $C\to D\to E\to C$ or $C\to E\to E\to C\;.$ Either works to give a tournament with the score sequence $\langle 0,1,3,3,3\rangle$.