# Tournament

An oriented graph (cf. also Graph, oriented) without loops, each pair of vertices of which are joined by an arc in exactly one direction. A tournament with $n$ vertices can be regarded as the outcome of a competition with $n$ players, the rules of which forbid draws. The notion of a tournament is used for ordering $n$ objects by the method of pairwise comparison. In this connection it finds application in biology, sociology, etc.

A tournament is said to be transitive if its vertices can be indexed by the numbers $1 \dots n$ in such a way that there is an arc going from $v _ {i}$ to $v _ {j}$ if and only if $i > j$. There are no circuits in a transitive tournament. A tournament is said to be strong if for any ordered pair of vertices $v _ {i} , v _ {j}$ there exists a directed path from $v _ {i}$ to $v _ {j}$. A set of arcs in a tournament is called compatible if there are no circuits in the subgraph formed by these arcs and the vertices incident to them. The maximum cardinality of a set of compatible arcs is a measure of compatibility in the definition of "the winner" of the tournament. Every tournament contains a subset of compatible arcs of cardinality not less than $( n ^ {2} /4) ( 1 + o ( 1))$. Another measure of compatibility is the ratio of the number of transitive $k$- vertex subtournaments of a tournament with $n$ vertices to the number of strong $k$- vertex subtournaments. The maximum number of strong $k$- vertex subtournaments of a tournament with $n$ vertices is equal to

$$\left ( \begin{array}{c} n \\ k \end{array} \right ) - k \left ( \begin{array}{c} ( n - 1)/2 \\ k \end{array} \right ) \ \ \textrm{ if } n \textrm{ is odd },$$

$$\left ( \begin{array}{c} n \\ k \end{array} \right ) - { \frac{k}{2} } \left \{ \left ( \begin{array}{c} n/2 \\ kh \end{array} \right ) - \left ( \begin{array}{c} ( n - 2)/2 \\ k - 1 \end{array} \right ) \right \} \ \textrm{ if } n \textrm{ is even }.$$

A tournament is strong if and only if it has a spanning cycle (Hamiltonian circuit). Every strong tournament with $n$ vertices has a circuit of length $k$ for $k = 3 \dots n$. Every tournament has a spanning path (Hamiltonian path).

The outdegrees $d _ {i}$ of a tournament with $n$ vertices satisfy the equation

$$\sum _ {i = 1 } ^ { n } d _ {i} ^ {2} = \ \sum _ {i = 1 } ^ { n } ( n - d _ {i} ) ^ {2} .$$

Suppose that a set of integers $( d _ {1} \dots d _ {n} )$ satisfies the condition $0 \leq d _ {1} \leq \dots \leq d _ {n} \leq n - 1$. Then a tournament with outdegrees $d _ {1} \dots d _ {n}$ exists if and only if for any $k = 1 \dots n - 1$ the inequality

$$\sum _ {i = 1 } ^ { k } d _ {i} \geq { \frac{k ( k - 1) }{2} }$$

holds, with equality for $k = n$. Furthermore, a tournament is strong if and only if

$$\sum _ {i = 1 } ^ { k } d _ {i} > \ { \frac{k ( k - 1) }{2} } \ \ \textrm{ for } k < n.$$

If $T _ {1}$ and $T _ {2}$ are two subtournaments of a tournament $T$ and if there exists an arc $( v ^ \prime , v ^ {\prime\prime} )$ for each pair of vertices $v ^ \prime$ in $T _ {1}$ and $v ^ {\prime\prime}$ in $T _ {2}$, then one writes $T _ {1} \rightarrow T _ {2}$. Suppose that the set of vertices of a tournament is partitioned into non-intersecting subsets $T _ {1} \dots T _ {m}$. Suppose further that either $T _ {i} \rightarrow T _ {j}$ or $T _ {j} \rightarrow T _ {i}$ for $1 \leq i \leq j \leq m$. Then the partition defines an equivalence relation on the vertices of $T$. A tournament is called simple if no non-trivial equivalence relation can be defined on its vertices. Every tournament with $n$ vertices is a subtournament of some simple tournament with $n + 2$ vertices. A tournament $T$ with $n$ vertices is a subtournament of some simple tournament with $n + 1$ vertices if and only if $T$ is neither a circuit with three vertices nor a non-trivial transitive tournament with an odd number of vertices. The number of pairwise non-isomorphic tournaments with $n$ vertices is asymptotically equal to

$${ \frac{1}{n!} } 2 ^ {\left ( \begin{array}{c} n \\ 2 \end{array} \right ) } .$$

The number of distinct tournaments with $n$ indexed vertices is equal to

$$2 ^ {\left ( \begin{array}{c} n \\ 2 \end{array} \right ) } .$$

The generating functions $t ( x)$ and $s ( x)$ for tournaments and strong tournaments, respectively, are related by the formula:

$$s ( x) = \frac{t ( x) }{1 + t ( x) } .$$

Every tournament with $n$ vertices, $n \geq 5$, that is not strong is uniquely recoverable from the family of its $( n- 1)$- vertex subtournaments.

How to Cite This Entry:
Tournament. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Tournament&oldid=49004
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article