Tournament (graph theory)

	Tournament
	; A tournament on 4 vertices
Vertices	n
Edges
	This box: view • talk • edit

From Wikipedia, the free encyclopedia

(Redirected from Tournament (mathematics))

Jump to: navigation, search

A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph.

Tournaments were originally used by Landau to model dominance relations in flocks of chickens. Current applications of tournaments include the study of voting theory and social choice theory among other things. 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. In the tournament digraph, the vertices correspond to the players. The edge between each pair of players is oriented from the winner to the loser. If player $a$ beats player $b$ , then it is said that $a$ dominates $b$ .

[edit] Paths and cycles

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 $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 for every $j \leq i$ there is a directed edge from $v j$ to $v 0$ . Then

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

is a directed path as desired.

A tournament on n vertices is strongly connected if and only if every vertex is on a cycle of length k for $3 \geq k \geq n$ . This implies that a strongly connected tournament 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).

[edit] Transitivity

A transitive tournament on 8 vertices.

A tournament in which $(a \rightarrow c$ and $b \rightarrow c)$ $\Rightarrow$ $(a \rightarrow c)$ is called transitive. The following statements are equivalent for a tournament T on n vertices:

T is transitive
T is acyclic
The score sequence for a transitive tournament is {0,1,2,...,n-1}
T has exactly one Hamiltonian path.

Every tournament on n vertices has a transitive subtournament on $log 2 (n)$ vertices. Reid and Parker showed that this is the best possible result. That is in general you can find a tournament on n vertices whose largest subtournament is of size $log 2 (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 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] Score Sequences and Score Sets

The score sequence of a tournament is the nondecreasing sequence of outdegrees of the vertices of a tournament. The score set of a tournament is the set of integers that are the outdegrees of vertices in that tournament.

Landau's Theorem(1953)Landau's Theorem(1953) A nondecreasing sequence of integers $(s_1, s_2, \cdots, s_n)$ is a score sequence if and only if :

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

Let $s (n)$ be the number of different score sequences 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, ...

Winston and Kleitman proved that for sufficiently large n:

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

where $c 1 = 0.049.$ Takács later showed, using some reasonable but unproven assumptions, that

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

where $c 2 < 4.858.$

Together these provide evidence that:

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

Here $Θ$ signifies an asymptotically tight bound.

Yao showed that every nonempty set of nonnegative integers is the score set for some tournament.

[edit] References

Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged 7: 39–43
Camion, Paul (1959), "Chemie et circuits hamiltoniens des graphes complets", Comptes Rendus de l'Académie des Sciences de Paris 249: 2151–2152
Thomassen, Carsten (1980), "Hamiltonian-Connected Tournaments", Journal of Combinatorial Theory, Series B 28: 142–163, doi:10.1016/0095-8956(80)90061-1
Takacs, Lajos (1991). "A Bernoulli Excursion and Its Various Applications". Advances in Applied Probability 23 (3): 557–585. doi:10.2307/1427622.
Reid, K.B (1970), "Disproof of a conjecture of Erdös and Moser", J . Combin. Theory.: 225–238
Yao, T.X. (1989), "On Reid Conjecture Of Score Sets For Tournaments", Chinese Sci. Bull. 34: 804–808

Landau, H. G. On dominance relations and the structure of animal societies. III. The condition for a score structure. Bull. Math. Biophys. 15, (1953)

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

Tournament (graph theory)

From Wikipedia, the free encyclopedia

Contents

[edit] Paths and cycles

[edit] Transitivity

[edit] Score Sequences and Score Sets

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox

Languages

Tournament
A tournament on 4 vertices
Vertices	$n$
Edges	$\binom{n}{2}$
This box: view • talk • edit