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 vertices can be regarded as the outcome of a competition with players, the rules of which forbid draws. The notion of a tournament is used for ordering 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 in such a way that there is an arc going from to if and only if . There are no circuits in a transitive tournament. A tournament is said to be strong if for any ordered pair of vertices there exists a directed path from to . 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 . Another measure of compatibility is the ratio of the number of transitive -vertex subtournaments of a tournament with vertices to the number of strong -vertex subtournaments. The maximum number of strong -vertex subtournaments of a tournament with vertices is equal to

A tournament is strong if and only if it has a spanning cycle (Hamiltonian circuit). Every strong tournament with vertices has a circuit of length for . Every tournament has a spanning path (Hamiltonian path).

The outdegrees of a tournament with vertices satisfy the equation

Suppose that a set of integers satisfies the condition . Then a tournament with outdegrees exists if and only if for any the inequality

holds, with equality for . Furthermore, a tournament is strong if and only if

If and are two subtournaments of a tournament and if there exists an arc for each pair of vertices in and in , then one writes . Suppose that the set of vertices of a tournament is partitioned into non-intersecting subsets . Suppose further that either or for . Then the partition defines an equivalence relation on the vertices of . A tournament is called simple if no non-trivial equivalence relation can be defined on its vertices. Every tournament with vertices is a subtournament of some simple tournament with vertices. A tournament with vertices is a subtournament of some simple tournament with vertices if and only if 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 vertices is asymptotically equal to

The number of distinct tournaments with indexed vertices is equal to

The generating functions and for tournaments and strong tournaments, respectively, are related by the formula:

Every tournament with vertices, , that is not strong is uniquely recoverable from the family of its -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 is defined by making random choices of an arc or for each pair of different vertices , 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)