Tournament

A complete oriented graph (Skiena 1990, p. 175), i.e., a graph in which every pair of nodes is connected by a single uniquely directed edge. The first and second 3-node tournaments shown above are called a transitive triple and cyclic triple, respectively (Harary 1994, p. 204).

Tournaments (also called tournament graphs) are so named because an -node tournament graph correspond to a tournament in which each member of a group of  players plays all other  players, and each game results in a win for one player and a loss for the other. A so-called score sequence can be associated with every tournament giving the set of scores that would be obtained by the players in the tournament, with each win counting as one point and each loss counting as no points. (A different scoring system is used to compute a tournament's so-called tournament matrix, with 1 point awarded for a win and  points for a loss.) The score sequence for a given tournament is obtained from the set of outdegrees sorted in nondecreasing order.

The number  of nonisomorphic tournaments on , 3, 4, ... nodes are 1, 2, 4, 12, 56, 456, ... (OEIS A000568; Moon 1968; Goldberg and Moon 1970; Harary and Palmer 1973, pp. 126 and 245; Reid and Beineke 1978). Davis (1954) and Harary (1957) obtained a formula for these numbers as a function of  using the Pólya enumeration theorem. For a symmetric group , define

(1)

where

(2)

with  the number of group elements in the conjugacy class of  in , and  is the number of cycles of length  in the disjoint-cycle representation of any member of the class. Define

(3)

where  is the greatest common divisor of  and . Then

(4)

(Davis 1954).

Every tournament contains an odd number of Hamiltonian paths (Rédei 1934; Szele 1943; Skiena 1990, p. 175). However, a tournament has a directed Hamiltonian cycle iff it is strongly connected (Foulkes 1960; Harary and Moser 1966; Skiena 1990, p. 175).

The term "tournament" also refers to an arrangement by which teams or players play against certain other teams or players in order to determine who is the best. In a "cup" tournament of  teams, teams play pairwise in a sequence of -finals, ..., 1/8-finals, quarterfinals, semifinals, and finals, with winners from each round playing other winners in the next round and losers being eliminated at each round. The second-place prize is usually awarded to the team that loses in the finals. However, this practice is unfair since the second-place team has not been required to play against the teams that were eliminated by the first-place (and presumably best) team, and therefore might actually be worse than one of the teams eliminated earlier by the best team (Steinhaus 1999).

In general, to fairly determine the best two players from  contestants,  rounds are required (Steinhaus 1999, p. 55).

REFERENCES

Boesch, F. and Tindell, R. "Robbins' Theorem for Mixed Graphs." Amer. Math. Monthly 87, 716-719, 1980.

Chartrand, G. "Tournaments." §27.2 in Introductory Graph Theory. New York: Dover, pp. 155-161, 1985.

Chvátal, V. and Thomassen, C. "Distances in Orientations of Graphs." J. Combin. Th. B 24, 61-75, 1978.

Davis, R. L. "Structure of Dominance Relations." Bull. Math. Biophys. 16, 131-140, 1954.

Foulkes, J. D. "Directed Graphs and Assembly Schedules." In Proc. Symp. Appl. Math. Providence, RI: Amer. Math. Soc., pp. 218-289, 1960.

Goldberg, M. and Moon, J. W. "On the Composition of Two Tournaments." Duke Math. J. 37, 323-332, 1970.

Harary, F. "The Number of Oriented Graphs." Mich. Math. J. 4, 221-224, 1957.

Harary, F. "Tournaments." In Graph Theory. Reading, MA: Addison-Wesley, pp. 204-208, 1994.

Harary, F. and Moser, L. "The Theory of Round Robin Tournaments." Amer. Math. Monthly 73, 231-246, 1966.

Harary, F. and Palmer, E. M. "On the Problem of Reconstructing a Tournament from Subtournaments." Monatsh. für Math. 71, 14-23, 1967.

Harary, F. and Palmer, E. M. "Tournaments." §5.2 in Graphical Enumeration. New York: Academic Press, pp. 124-127, 1973.

Moon, J. W. Topics on Tournaments. New York: Holt, Rinehart, and Winston, p. 87, 1968.

Ore, Ø. Graphs and Their Uses. New York: Random House, 1963.Rédei, L. "Ein Kombinatorischer Satz." Acta Litt. Szeged. 7, 39-43, 1934.

Reid, K. B. and Beineke, L. W. "Tournaments." In Selected Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson). New York: Academic Press, pp. 169-204, 1978.

Roberts, F. S. Graph Theory and Its Applications to Problems of Society. Philadelphia, PA: SIAM, 1978.

Ruskey, F. "Information on Score Sequences." http://www.theory.csc.uvic.ca/~cos/inf/nump/ScoreSequence.html.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Sloane, N. J. A. Sequence A000568/M1262 in "The On-Line Encyclopedia of Integer Sequences."Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 54-55, 1999.

Szele, T. "Kombinatorische Untersuchungen über den gerichteten vollständigen Graphen." Mat. Fiz. Lapok 50, 223-256, 1943.