Open main menu

A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is an orientation of a complete graph, or equivalently a directed graph in which every pair of distinct vertices is connected by a single directed edge.

Tournament
4-tournament.svg
A tournament on 4 vertices
Vertices
Edges
Table of graphs and parameters

Many of the important properties of tournaments were first investigated by Landau (1953) in order to model dominance relations in flocks of chickens. Current applications of tournaments include the study of voting theory and social choice theory among other things. The name tournament originates from such a graph's interpretation as the outcome of a round-robin tournament in which every player encounters every other player exactly once, and in which no draws occur. In the tournament digraph, the vertices correspond to the players. The edge between each pair of players is oriented from the winner to the loser. If player beats player , then it is said that dominates . If every player beats the same number of other players (indegree = outdegree), the tournament is called regular.

Contents

Paths and cyclesEdit

Any tournament on a finite number   of vertices contains a Hamiltonian path, i.e., directed path on all   vertices (Rédei 1934). This is easily shown by induction on  : suppose that the statement holds for  , and consider any tournament   on   vertices. Choose a vertex   of   and consider a directed path   in  . Now let   be maximal such that for every   there is a directed edge from   to  .

 

is a directed path as desired. This argument also gives an algorithm for finding the Hamiltonian path. More efficient algorithms, that require examining only   of the edges, are known.[1]

This implies that a strongly connected tournament has a Hamiltonian cycle (Camion 1959). More strongly, every strongly connected tournament is vertex pancyclic: for each vertex  , and each   in the range from three to the number of vertices in the tournament, there is a cycle of length   containing  .[2] Moreover, if the tournament is 4‑connected, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980).

TransitivityEdit

 
A transitive tournament on 8 vertices.

A tournament in which   and       is called transitive. In other words, in a transitive tournament, the vertices may be (strictly) totally ordered by the edge relation, and the edge relation is the same as reachability.

Equivalent conditionsEdit

The following statements are equivalent for a tournament   on   vertices:

  1.   is transitive.
  2.   is a strict total ordering.
  3.   is acyclic.
  4.   does not contain a cycle of length 3.
  5. The score sequence (set of outdegrees) of   is  .
  6.   has exactly one Hamiltonian path.

Ramsey theoryEdit

Transitive tournaments play a role in Ramsey theory analogous to that of cliques in undirected graphs. In particular, every tournament on   vertices contains a transitive subtournament on   vertices.[3] The proof is simple: choose any one vertex   to be part of this subtournament, and form the rest of the subtournament recursively on either the set of incoming neighbors of   or the set of outgoing neighbors of  , whichever is larger. For instance, every tournament on seven vertices contains a three-vertex transitive subtournament; the Paley tournament on seven vertices shows that this is the most that can be guaranteed (Erdős & Moser 1964). However, Reid & Parker (1970) showed that this bound is not tight for some larger values of  .

Erdős & Moser (1964) proved that there are tournaments on   vertices without a transitive subtournament of size   Their proof uses a counting argument: the number of ways that a  -element transitive tournament can occur as a subtournament of a larger tournament on   labeled vertices is

 

and when   is larger than  , this number is too small to allow for an occurrence of a transitive tournament within each of the   different tournaments on the same set of   labeled vertices.

Paradoxical tournamentsEdit

A player who wins all games would naturally be the tournament's winner. However, as the existence of non-transitive tournaments shows, there may not be such a player. A tournament for which every player loses at least one game is called a 1-paradoxical tournament. More generally, a tournament   is called  -paradoxical if for every  -element subset   of   there is a vertex   in   such that   for all  . By means of the probabilistic method, Paul Erdős showed that for any fixed value of  , if  , then almost every tournament on   is  -paradoxical.[4] On the other hand, an easy argument shows that any  -paradoxical tournament must have at least   players, which was improved to   by Esther and George Szekeres (1965).[5] There is an explicit construction of  -paradoxical tournaments with   players by Graham and Spencer (1971) namely the Paley tournament.

CondensationEdit

The condensation of any tournament is itself a transitive tournament. Thus, even for tournaments that are not transitive, the strongly connected components of the tournament may be totally ordered.[6]

Score sequences and score setsEdit

The score sequence of a tournament is the nondecreasing sequence of outdegrees of the vertices of a tournament. The score set of a tournament is the set of integers that are the outdegrees of vertices in that tournament.

Landau's Theorem (1953) A nondecreasing sequence of integers   is a score sequence if and only if :

  1.  
  2.  
  3.  

Let   be the number of different score sequences of size  . The sequence   (sequence A000571 in the OEIS) starts as:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

Winston and Kleitman proved that for sufficiently large n:

 

where   Takács later showed, using some reasonable but unproven assumptions, that

 

where  

Together these provide evidence that:

 

Here   signifies an asymptotically tight bound.

Yao showed that every nonempty set of nonnegative integers is the score set for some tournament.

Majority relationsEdit

In social choice theory, tournaments naturally arise as majority relations of preference profiles.[7] Let   be a finite set of alternatives, and consider a list   of linear orders over  . We interpret each order   as the preference ranking of a voter  . The (strict) majority relation   of   over   is then defined so that   if and only if a majority of the voters prefer   to  , that is  . If the number   of voters is odd, then the majority relation forms the dominance relation of a tournament on vertex set  .

By a lemma of McGarvey, every tournament on   vertices can be obtained as the majority relation of at most   voters.[7][8] Results by Stearns and Erdős & Moser later established that   voters are needed to induce every tournament on   vertices.[9]

Laslier (1997) studies in what sense a set of vertices can be called the set of "winners" of a tournament. This revealed to be useful in Political Science to study, in formal models of political economy, what can be the outcome of a democratic process.[10]

See alsoEdit

NotesEdit

  1. ^ Bar-Noy & Naor (1990).
  2. ^ Moon (1966), Theorem 1.
  3. ^ Erdős & Moser (1964).
  4. ^ Erdős (1963)
  5. ^ Szekeres, E.; Szekeres, G. (1965). "On a problem of Schütte and Erdős". Math. Gaz. 49: 290–293. 
  6. ^ Harary & Moser (1966), Corollary 5b.
  7. ^ a b Brandt, Felix and Brill, Markus and Harrenstein, Paul, "Tournament Solutions". Chapter 3 in: Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432.  (free online version)
  8. ^ McGarvey, David C. (1953-01-01). "A Theorem on the Construction of Voting Paradoxes". Econometrica. 21 (4): 608–610. doi:10.2307/1907926. JSTOR 1907926. 
  9. ^ Stearns, Richard (1959-01-01). "The Voting Problem". The American Mathematical Monthly. 66 (9): 761–763. doi:10.2307/2310461. JSTOR 2310461. 
  10. ^ Austen-Smith, D. and J. Banks, Positive Political theory, 1999, The University of Michigan Press.

ReferencesEdit

This article incorporates material from tournament on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.