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.

References[edit]

Comments[edit]

A random tournament over $ N = \{ 1 \dots n \} $ is defined by making random choices of an arc $ {x _ {i} x _ {j} } vec $ or $ {x _ {j} x _ {i} } vec $ for each pair of different vertices $ x _ {i} , x _ {j} $, the choice being equiprobable and independent for all different pairs. Cf. [2] for many results on random tournaments.

References[edit]