Can a Tournament Graph Define a Total Order Without Three-Player Cycles?

[QuietMind]

Homework Statement

In an n-player round-robin tournament, every pair of distinct players compete in a single game. Assume that every game has a winner —there are no ties. The results of such a tournament can then be represented with a tournament digraph where the vertices correspond to players and there is an edge x→y iff x beat y in their game.

(a) Explain why a tournament digraph cannot have cycles of length 1 or 2.

(b) Is the “beats” relation for a tournament graph always/sometimes/never: • asymmetric? • reflexive? • irreflexive? • transitive? Explain.

(c) Show that a tournament graph represents a total order iff there are no cycles of length 3.

Homework Equations

The Attempt at a Solution

I'm struggling with part c. I have the solutions posted below, but I don't fully understand the explanation.

"As observed in the previous part, the “beats” relation whose graph is a tournament is asymmetric and irreflexive. Since every pair of players is comparable, the relation is a total order iff it is transitive. “Beats” is transitive iff for any players x, y and z, x → y and y → z implies that x → z (and consequently that there is no edge z x). Therefore, “beats” is transitive iff there are no cycles of length 3. "

I do not understand "Since every pair of players is comparable, the relation is a total order iff it is transitive." I thought that total order simply meant that any two players have to be comparable, so A beats B or B beats A. To me, that seems to be satisfied by the fact that it is a round robin tournament. The answer seems to imply that this total order implies there's a hierarchy of who beats who. How do they get transitivity from the stipulation that it's a total order?

 

[andrewkirk]

I thought that total order simply meant that any two players have to be comparable, so A beats B or B beats A.

That's close, but not quite correct. A more accurate statement is 'a partial order on a set is also a total order on that set if for any two elements there is an order relation between them'.

A (strict) partial order is a binary relation on a set that is transitive, irreflexive and asymmetric. So without transitivity the relation is not even a partial order. It is not any sort of order relation. The 'strict' part relates to asymmetric and irreflexive properties. Without those it is a non-strict partial order. It's the difference between $<$ and $\leq$.

Since every player plays every other, the completeness requirement of a total order is already satisfied, and the earlier questions established irreflexivity and asymmetry. The only part that is not yet established, to qualify as an order (and therefore also as a total order) is transitivity.