Acyclic Tournament Digraphs and Hamiltonian Paths

Question

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.

Answer 1

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.

Answer 2

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