TOPICS
Search

Tournament


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 n-node tournament graph correspond to a tournament in which each member of a group of n players plays all other n-1 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 -1 points for a loss.) The score sequence for a given tournament is obtained from the set of outdegrees sorted in nondecreasing order.

The number a(n) of nonisomorphic tournaments on n=2, 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 n using the Pólya enumeration theorem. For a symmetric group S_n, define

 s(pi)={0   if pi has any cycle of even length; n(pi)   otherwise,
(1)

where

 n(pi)=(c(pi))/(n!)=1/(1^(p_1)p_1!2^(p_2)p_2!...n^(p_n)p_n!),
(2)

with c(pi) the number of group elements in the conjugacy class of pi in S_n, and p_k is the number of cycles of length k in the disjoint-cycle representation of any member of the class. Define

 d(pi)=1/2sum_(i=1)^np_i(ip_i-1)-sum_(i<j)p_jp_jGCD(i,j),
(3)

where GCD(i,j) is the greatest common divisor of i and j. Then

 a(n)=sums(pi)2^(d(pi))
(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 n=2^k teams, teams play pairwise in a sequence of 1/2^(k-1)-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 n contestants, n-1+log_2(n-1) rounds are required (Steinhaus 1999, p. 55).


See also

Complete Graph, Cyclic Triple, Directed Graph, Hamiltonian Path, Score Sequence, Tournament Matrix, Transitive Triple

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Tournament

Cite this as:

Weisstein, Eric W. "Tournament." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Tournament.html

Subject classifications