1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Total Order Properties

  1. Apr 12, 2016 #1
    1. The problem statement, all variables and given/known data
    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.

    2. Relevant equations


    3. 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?
     
  2. jcsd
  3. Apr 12, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Total Order Properties
  1. Proving Total Order (Replies: 6)

Loading...