Total Order Properties

  • Thread starter QuietMind
  • Start date
  • #1
42
2

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?
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,851
1,433
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.
 
  • Like
Likes QuietMind

Related Threads on Total Order Properties

  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
4
Views
844
  • Last Post
Replies
4
Views
2K
Replies
3
Views
992
Replies
4
Views
748
Replies
10
Views
3K
Replies
0
Views
2K
Replies
1
Views
818
Top