3
$\begingroup$

I am studying MIT OCW lecture notes but they do not have solutions for the following problem.

Directed Acyclic Tournaments

In a round-robin tournament, every two distinct players play against each other just once. For a round-robin tournament with no tied games, a record of who beat whom can be described with a tournament digraph, where the vertices correspond to players and there is an edge $x \rightarrow y$ iff $x$ beat $y$ in their game.

A ranking is a path that includes all the players. So in a ranking, each player won the game against the next lowest ranked player, but may very well have lost their games against much lower ranked players —whoever does the ranking may have a lot of room to play favorites.

  1. Give an example of a tournament digraph with more than one ranking.
  2. Prove that if a tournament digraph is a DAG, then it has at most one ranking.
  3. Prove that every finite tournament digraph has a ranking.
  4. Prove that the greater-than relation, $>$, on the rational numbers, $Q$, is a DAG and a tournament graph that has no ranking.

I got stuck at questions 2, 3, and 4. I have no idea how to solve it. I tried induction on b without a luck but still induction does not even help for infinite DAG cases.

$\endgroup$
  • $\begingroup$ There are lots of OCW lecture notes, even for the same course in different terms. $\endgroup$ – vonbrand Mar 9 '13 at 22:25
  • $\begingroup$ so what do you mean ? $\endgroup$ – asd Mar 9 '13 at 23:31
  • 2
    $\begingroup$ @vonbrand, that may very well be true, but OP gave all the required information regarding the problem statement, and his/her troubles. $\endgroup$ – Nicholas Mancuso Mar 9 '13 at 23:42
3
$\begingroup$

I am completing Nicholas's answer because I think there are problems with his answers to 3 and 4 and explaining why is a bit too long for comments.

For 3. you need to show there is a simple path in the tournament that visits every vertex (this is called a hamiltonian path). You can do this simply by induction. Clearly this is true for a tournament on 2 vertices. Now assume you have a tournament $T = (V, A)$ on $n$ vertices. Remove some arbitrary $v$ from $V$ and find a hamiltonian path $v_1, \ldots, v_{n-1}$ in the induced tournament on $V \setminus \{v\}$. If for all $i \leq n-1$, $(v_i, v) \in A$, then $(v_{n-1}, v) \in A$ and you can append $v$ to the existing path. Otherwise, there exists some edge from $v$ to the $\{v_1, \ldots, v_{n-1}\}$; let $i$ be the smallest integer such that $(v, v_i) \in A$. Either $i = 1$ and you can pre-pend $v$ to the existing path, or, since $i$ was the smallest $i$ such that $(v, v_i) \in A$, you know that $(v_{i-1}, v) \in A$, and, therefore, you can take the path $v_1, \ldots, v_{i-1}, v, v_i, v_{i+1}, \ldots, v_{n-1}$.

For 4., I also don't think it's enough to say that the rationals have no infimum or supremum. That's true of the integers too, but there exists a path through the integers which is infinite in both directions. I think the crucial property of the rationals that causes problems is that they are dense: there is a rational between every two rationals. In particular, assume for contradiction there exists a path that visits all rationals in the graph defined in the question. Take any edge $(x, y)$ in the path: $x < \frac{x+y}{2} <y$, so $\frac{x+y}{2}$ cannot precede $x$ in the path and it cannot succeed $y$, so it cannot be in the path - a contradiction.

$\endgroup$
1
$\begingroup$

For clarity let $T= (V,E)$ be a tournament and let $a \rightsquigarrow b$ denote a path from $a$ to $b$ in $T$.

  1. A simple directed cycle clearly gives a tournament with more than one ranking.
  2. Suppose there is more than one ranking. Then there exists subpaths $a \rightsquigarrow b$ and $b \rightsquigarrow a$ in their respective rankings. This implies a cycle in the original tournament $T$, which contradicts the fact that $T$ is a DAG.
  3. Topologically sort $T$. Suppose $v_i, \rightsquigarrow v_{i+1}$ does not hold under this ordering. Then by definition of DAG $v_{i+1} \rightsquigarrow v_i$ must be true. But this is a contradiction with our topological ordering.
  4. I may be wrong, but there must be a "winner" (i.e. supremum) in a tournament and there is no such rational number in $\mathbb{Q}$.
$\endgroup$
  • $\begingroup$ Then there exists subpaths $a \rightsquigarrow b$ and $b \rightsquigarrow a$ in their respective rankings. Why ? may be other ranking is still valid with non swapped a,b. why does it has to swap a,b? $\endgroup$ – asd Mar 10 '13 at 0:21
  • $\begingroup$ There has to be some part of the path that is different, otherwise its the same ranking. $\endgroup$ – Nicholas Mancuso Mar 10 '13 at 0:22
  • $\begingroup$ 3. makes no sense to me, you need to prove that every tournament has a hamiltonian path. that's a nice exercise in induction, you just need to think about extending a path on a subgraph induced by $V\setminus \{v\}$ for an arbitrary $v$. prove that you can always "insert" $v$ somewhere. $\endgroup$ – Sasho Nikolov Mar 10 '13 at 5:28
  • 1
    $\begingroup$ 4 doesn't make sense, consider $\mathbb{N}$. Maybe you want to say that $(\mathbb{Q},<) \not \cong (\mathbb{N}, <)$? $\endgroup$ – Pål GD Mar 10 '13 at 8:08
  • $\begingroup$ @SashoNikolov, yeah. I was trying to show that there will always be a path from some $v_1$ to $v_n$. Induction would be a much cleaner way. $\endgroup$ – Nicholas Mancuso Mar 10 '13 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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