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:

Image:Tournament (graph theory).png

The name tournament originates from such a graph's interpretation as the outcome of a round-robin tournament 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 (Rédei 1934). 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 v0 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 (Camion 1959). Moreover, if the tournament is 4‑connected, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980).

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.

[edit] Number of possible results

Let us have n competitors, and a scoring system where no ties are permitted. Let si be the number of wins scored by competitor i, and let us order them such that s_1 \le s_2 \le \cdots \le s_n. Thus we define a score vector, (s_1, s_2, \cdots, s_n), satisfying the following three conditions:

  1. 0 \le s_1 \le s_2 \le \cdots \le s_n
  2. s_1 + s_2 + \cdots + s_i \ge {i \choose 2}, \mbox{for }i = 1, 2, \cdots, n - 1
  3. s_1 + s_2 + \cdots + s_n = {n \choose 2}

Let s(n) be the number of different score vectors of size n. The sequence s(n) (sequence A000571 in OEIS) starts as:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

It is possible to show that for sufficiently large n:

s(n) > c_1 4^n n^{-{5 \over 2}}

Also:

s(n) < c_2 4^n n^{-{5 \over 2}}

Where: c_1 = 0.049,\,\, c_2 < 4.858.

Together these show that:

s(n) \in \Theta (4^n n^{-{5 \over 2}}).

Here Θ signifies an asymptotically tight bound.

[edit] References

  • Rédei, László (1934), “Ein kombinatoriſcher Satz”, Acta Litteraria Szeged 7: 39–43 
  • Camion, Paul (1959), “Chemie et circuits hamiltoniens des graphes complets”, Comptes Rendus de la Académie des Sciences de Paris 249: 2151–2152 
  • Thomassen, Carsten (1980), “Hamiltonian-Connected Tournaments”, Journal of Combinatorial Theory, Series B 28: 142–163 
  • Takacs, Lajos (1991). "A Bernoulli Excursion and Its Various Applications". Advances in Applied Probability 23 (3): 557-585. doi:10.2307/1427622. 

This article incorporates material from tournament on PlanetMath, which is licensed under the GFDL.

Languages