Tournament (graph theory)

From Wikipedia, the free encyclopedia

A tournament is a directed graph obtained by choosing a direction for each edge in an undirected complete graph. For example, here is a tournament on 4 vertices:

The name tournament originates from such a graph's interpretation as the outcome of some sports competition in which every player encounters every other player exactly once, and in which no draws occur; let us say that an arrow points from the winner to the loser. If player $a$ beats player $b$ , then it is said that $a$ dominates $b$ .

Any tournament on a finite number $n$ of vertices contains a Hamiltonian path, i.e., directed path on all $n$ vertices. This is easily shown by induction on $n$ : suppose that the statement holds for $n$ , and consider any tournament $T$ on $n + 1$ vertices. Choose a vertex $v 0$ of $T$ and consider a directed path $v_1,v_2,\ldots,v_n$ in $T\setminus \{v_0\}$ . Now let $i \in \{0,\ldots,n\}$ be maximal such that $v_j \rightarrow v_0$ for all $j$ with $1 \leq j \leq i$ . Then

$v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n$

is a directed path as desired.

Similarly, any strongly connected tournament on $n \geq 3$ vertices contains cycles of length $3,\dots,n$ . As a corollary, a tournament is strongly connected if and only if it has a Hamiltonian cycle.

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 there isn't is called a $1$ -paradoxical tournament. More generally, a tournament $T = (V, E)$ is called $k$ -paradoxical if for every $k$ -subset $V'$ of $V$ there is a $v_0 \in V \setminus V'$ such that $v_0 \rightarrow v$ for all $v \in V'$ . By means of the probabilistic method Paul Erdős showed that if $\vert V\vert$ is sufficiently large, then almost every tournament on $V$ is $k$ -paradoxical.