Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from mathematica.stackexchange.com Oct 21 '12 at 22:49

This question came from our site for users of Mathematica.

    
Are you sure your question is related to Mathematica (TM) "the software"? –  belisarius Oct 21 '12 at 22:41
    
@belisarius Yes, here is a similar question on the same forum math.stackexchange.com/questions/145662/… –  Pavel Podlipensky Oct 21 '12 at 22:54

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
I don't think C,D and E can form a cycle as no ties are allowed and each player plays only once with other. Here is a graph I'm trying to draw, but for the E there is no way to have 3 outbound edges without making a cycle with C or D: i49.tinypic.com/es0ls8.jpg –  Pavel Podlipensky Oct 21 '12 at 23:11
    
There is no requirement that the graph be acyclic. –  Rahul Oct 21 '12 at 23:16

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.