Tournament (graph Theory) - Transitivity

Transitivity

A tournament in which and is called transitive. The following statements are equivalent for a tournament T on n vertices:

1. T is transitive
2. T is acyclic
3. T does not contain a cycle of length 3
4. The score sequence (set of outdegrees) of T is {0,1,2,...,n − 1}.
5. T has exactly one Hamiltonian path.

Every tournament on n vertices has a transitive subtournament on log₂n vertices. Reid & Parker (1970) showed that this bound is not tight. Erdős & Moser (1964) also proved that there are tournaments on n vertices without a transitive subtournament of size 2log₂n.

A player who wins all games would naturally be the tournament's winner. However, as the above example shows, there might not be such a player. A tournament for which every player loses at least one game is called a 1-paradoxical tournament. More generally, a tournament T=(V,E) is called k-paradoxical if for every k-element subset S of V there is a vertex v₀ in such that for all . By means of the probabilistic method, Paul Erdős showed that for any fixed value of k, if |V| ≥ k22kln(2 + o(1)), then almost every tournament on V is k-paradoxical. On the other hand, an easy argument shows that any k-paradoxical tournament must have at least 2k+1 − 1 players, which was improved to (k + 2)2k−1 − 1 by Esther and George Szekeres (1965). There is an explicit construction of k-paradoxical tournaments with k24k−1(1 + o(1)) players by Graham and Spencer (1971) namely the Paley tournament.

The condensation of any tournament is itself a transitive tournament.