Namespaces
Variants
Actions

Tournament

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.


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

[1] F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[2] J.W. Moon, "Topics on tournaments" , Holt, Rinehart & Winston (1968)

Comments

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

[a1] F. Harary, L. Moser, "The theory of round robin tournaments" Amer. Math. Monthly , 73 (1966) pp. 231–246
[a2] L. Comtet, "Advanced combinatorics" , Reidel (1974) pp. 68ff (Translated from French)
How to Cite This Entry:
Tournament. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Tournament&oldid=52603
This article was adapted from an original article by A.A. Sapozhenko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article