Tournament
A tournament on 4 vertices
Vertices	${\displaystyle n}$
Edges	${\displaystyle (\genfrac{}{}{0ex}{}{n}{2})}$
Table of graphs and parameters

Ingraph theory, atournament is adirected graph with exactly one edge between each twovertices, in one of the two possible directions. Equivalently, a tournament is anorientation of anundirected complete graph. (However, as directed graphs, tournaments are not complete: complete directed graphs have two edges, in both directions, between each two vertices.^[1]) Equivalently, a tournament is acompleteasymmetricrelation.^[2][3]

The nametournament comes from interpreting the graph as the outcome of around-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser.

Many of the important properties of tournaments were investigated byH. G. Landau in 1953 to model dominance relations in flocks of chickens.^[4] Tournaments are also heavily studied invoting theory, where they can represent partial information about voter preferences among multiple candidates, and are central to the definition ofCondorcet methods.

If every player beats the same number of other players (indegree − outdegree = 0) the tournament is calledregular. The number of unlabeled regular tournaments with 2n+1 vertices goes:

1, 1, 1, 3, 15, 1223, 1495297, 18400989629, 2406183070160597,... (sequenceA096368 in theOEIS)

Any tournament on afinite number${\displaystyle n}$ of vertices contains aHamiltonian path, i.e., directed path on all${\displaystyle n}$ vertices (Rédei 1934).

This is easily shown byinduction on${\displaystyle n}$: suppose that the statement holds for${\displaystyle n}$, and consider any tournament${\displaystyle T}$ on${\displaystyle n+1}$ vertices. Choose a vertex${\displaystyle v_0}$ of${\displaystyle T}$ and consider a directed path${\displaystyle v_1,v_2,\dots ,v_n}$ in${\displaystyle T\setminus \{v_0\}}$. There is some${\displaystyle i\in \{0,\dots ,n\}}$ such that${\displaystyle (i=0\vee v_i\to v_0)\wedge (v_0\to v_{i+1}\vee i=n)}$. (One possibility is to let${\displaystyle i\in \{0,\dots ,n\}}$ be maximal such that for every${\displaystyle j\le i,v_j\to v_0}$. Alternatively, let${\displaystyle i}$ be minimal such that${\displaystyle \mathrm{\forall }j>i,v_0\to v_j}$.)$${\displaystyle v_1,\dots ,v_i,v_0,v_{i+1},\dots ,v_n}$$is a directed path as desired. This argument also gives an algorithm for finding the Hamiltonian path. More efficient algorithms, that require examining only${\displaystyle O(n\log n)}$ of the edges, are known. The Hamiltonian paths are in one-to-one correspondence with the minimalfeedback arc sets of the tournament.^[5] Rédei's theorem is the special case for complete graphs of theGallai–Hasse–Roy–Vitaver theorem, relating the lengths of paths in orientations of graphs to thechromatic number of these graphs.^[6]

Another basic result on tournaments is that everystrongly connected tournament has aHamiltonian cycle.^[7] More strongly, every strongly connected tournament isvertex pancyclic: for each vertex${\displaystyle v}$, and each${\displaystyle k}$ in the range from three to the number of vertices in the tournament, there is a cycle of length${\displaystyle k}$ containing${\displaystyle v}$.^[8] A tournament${\displaystyle T}$ is${\displaystyle k}$-strongly connected if for every set${\displaystyle U}$ of${\displaystyle k-1}$ vertices of${\displaystyle T}$,${\displaystyle T-U}$ is strongly connected. If the tournament is 4‑strongly connected, then each pair of vertices can be connected with a Hamiltonian path.^[9] For every set${\displaystyle B}$ of at most${\displaystyle k-1}$ arcs of a${\displaystyle k}$-strongly connected tournament${\displaystyle T}$, we have that${\displaystyle T-B}$ has a Hamiltonian cycle.^[10] This result was extended byBang-Jensen, Gutin & Yeo (1997).^[11]

A tournament in which${\displaystyle ((a\to b)}$ and${\displaystyle (b\to c))}$${\displaystyle \Rightarrow }$${\displaystyle (a\to c)}$ is calledtransitive. 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 asreachability.

The following statements are equivalent for a tournament${\displaystyle T}$ on${\displaystyle n}$ vertices:

1. ${\displaystyle T}$ is transitive.
2. ${\displaystyle T}$ is a strict total ordering.
3. ${\displaystyle T}$ isacyclic.
4. ${\displaystyle T}$ does not contain a cycle of length 3.
5. The score sequence (set of outdegrees) of${\displaystyle T}$ is${\displaystyle \{0,1,2,\dots ,n-1\}}$.
6. ${\displaystyle T}$ has exactly one Hamiltonian path.

Transitive tournaments play a role inRamsey theory analogous to that ofcliques in undirected graphs. In particular, every tournament on${\displaystyle n}$ vertices contains a transitive subtournament on${\displaystyle 1+\lfloor {\log }_{2}n\rfloor }$ vertices. The proof is simple: choose any one vertex${\displaystyle v}$ to be part of this subtournament, and form the rest of the subtournament recursively on either the set of incoming neighbors of${\displaystyle v}$ or the set of outgoing neighbors of${\displaystyle v}$, whichever is larger. For instance, every tournament on seven vertices contains a three-vertex transitive subtournament; thePaley tournament on seven vertices shows that this is the most that can be guaranteed.^[12] However,Reid & Parker (1970) showed that this bound is not tight for some larger values of ${\displaystyle n}$.^[13]

Erdős & Moser (1964) proved that there are tournaments on${\displaystyle n}$ vertices without a transitive subtournament of size${\displaystyle 2+2\lfloor {\log }_{2}n\rfloor }$ Their proof uses acounting argument: the number of ways that a${\displaystyle k}$-element transitive tournament can occur as a subtournament of a larger tournament on${\displaystyle n}$ labeled vertices is$${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})k!2^{(\genfrac{}{}{0ex}{}{n}{2})-(\genfrac{}{}{0ex}{}{k}{2})},}$$and when${\displaystyle k}$ is larger than${\displaystyle 2+2\lfloor {\log }_{2}n\rfloor }$, this number is too small to allow for an occurrence of a transitive tournament within each of the${\displaystyle 2^{(\genfrac{}{}{0ex}{}{n}{2})}}$ different tournaments on the same set of${\displaystyle n}$ labeled vertices.^[12]

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${\displaystyle T=(V,E)}$ is called${\displaystyle k}$-paradoxical if for every${\displaystyle k}$-element subset${\displaystyle S}$ of${\displaystyle V}$ there is a vertex${\displaystyle v_0}$ in${\displaystyle V\setminus S}$ such that${\displaystyle v_0\to v}$ for all${\displaystyle v\in S}$. By means of theprobabilistic method,Paul Erdős showed that for any fixed value of${\displaystyle k}$, if${\displaystyle |V|\ge k^2{2}^k\ln (2+o(1))}$, then almost every tournament on${\displaystyle V}$ is${\displaystyle k}$-paradoxical.^[14] On the other hand, an easy argument shows that any${\displaystyle k}$-paradoxical tournament must have at least${\displaystyle 2^{k+1}-1}$ players, which was improved to${\displaystyle (k+2)2^{k-1}-1}$ byEsther andGeorge Szekeres in 1965.^[15] There is an explicit construction of${\displaystyle k}$-paradoxical tournaments with${\displaystyle k^2{4}^{k-1}(1+o(1))}$ players byGraham and Spencer (1971) namely thePaley tournament.

Thecondensation 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.^[16]

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${\displaystyle (s_1,s_2,\dots ,s_n)}$ is a score sequence if and only if:^[4]

1. ${\displaystyle 0\le s_1\le s_2\le \cdots \le s_n}$
2. ${\displaystyle s_1+s_2+\cdots +s_i\ge (\genfrac{}{}{0ex}{}{i}{2}),\text{ for }i=1,2,\dots ,n-1}$
3. ${\displaystyle s_1+s_2+\cdots +s_n=(\genfrac{}{}{0ex}{}{n}{2}).}$

Let${\displaystyle s(n)}$ be the number of different score sequences of size${\displaystyle n}$. The sequence${\displaystyle s(n)}$ (sequenceA000571 in theOEIS) starts as:

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

Winston and Kleitman proved that for sufficiently largen:

${\displaystyle s(n)>c_1{4}^n{n}^{-5/2},}$

where${\displaystyle c_1=\mathrm{0.049.}}$Takács later showed, using some reasonable but unproven assumptions, that

where^[17]

Together these provide evidence that:

${\displaystyle s(n)\in \mathrm{\Theta }(4^n{n}^{-5/2}).}$

Here${\displaystyle \mathrm{\Theta }}$ signifies anasymptotically tight bound.

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

Insocial choice theory, tournaments naturally arise as majority relations of preference profiles.^[19] Let${\displaystyle A}$ be a finite set of alternatives, and consider a list${\displaystyle P=({\succ }_1,\dots ,{\succ }_n)}$ oflinear orders over${\displaystyle A}$. We interpret each order${\displaystyle {\succ }_i}$ as thepreference ranking of a voter${\displaystyle i}$. The (strict) majority relation${\displaystyle {\succ }_{\text{maj}}}$ of${\displaystyle P}$ over${\displaystyle A}$ is then defined so that${\displaystyle a{\succ }_{\text{maj}}b}$ if and only if a majority of the voters prefer${\displaystyle a}$ to${\displaystyle b}$, that is${\displaystyle |\{i\in [n]:a{\succ }_{i}b\}|>|\{i\in [n]:b{\succ }_{i}a\}|}$. If the number${\displaystyle n}$ of voters is odd, then the majority relation forms the dominance relation of a tournament on vertex set${\displaystyle A}$.

By a lemma of McGarvey, every tournament on${\displaystyle m}$ vertices can be obtained as the majority relation of at most${\displaystyle m(m-1)}$ voters.^[20] Results byStearns and Erdős & Moser later established that${\displaystyle \mathrm{\Theta }(m/\log m)}$ voters are needed to induce every tournament on${\displaystyle m}$ vertices.^[21]

Laslier (1997) studies in what sense a set of vertices can be called the set of "winners" of a tournament.^[22] This revealed to be useful inpolitical science to study, in formal models ofpolitical economy, what can be the outcome of a democratic process.^[23]

• Oriented graph
• Paley tournament
• Sumner's conjecture
• Tournament solution

• Austen-Smith, D.; Banks, J. (1999),Positive Political theory, University of Michigan Press
• Bang-Jensen, J.;Gutin, G.; Yeo, A. (1997), "Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments",Combinatorics, Probability and Computing,6 (3):255–261,doi:10.1017/S0963548397003027
• Bar-Noy, A.;Naor, J. (1990), "Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments",SIAM Journal on Discrete Mathematics,3 (1):7–20,doi:10.1137/0403002
• Brandt, Felix; Brill, Markus; Harrenstein, Paul (2016), "Chapter 3: Tournament Solutions", in Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (eds.),Handbook of Computational Social Choice, Cambridge University Press,ISBN 9781107060432
• Camion, Paul (1959),"Chemins et circuits hamiltoniens des graphes complets",Comptes Rendus de l'Académie des Sciences de Paris (in French),249:2151–2152
• Erdős, P. (1963),"On a problem in graph theory"(PDF),The Mathematical Gazette,47 (361):220–223,doi:10.2307/3613396,JSTOR 3613396,MR 0159319
• Erdős, P.;Moser, L. (1964),"On the representation of directed graphs as unions of orderings"(PDF),Magyar Tud. Akad. Mat. Kutató Int. Közl.,9:125–132,MR 0168494
• Fraisse, P.; Thomassen, C. (1987), "A constructive solution to a tournament problem",Graphs and Combinatorics,3:239–250,doi:10.1007/BF01788546.
• Graham, R. L.;Spencer, J. H. (1971), "A constructive solution to a tournament problem",Canadian Mathematical Bulletin,14:45–48,doi:10.4153/cmb-1971-007-1,MR 0292715.
• Harary, Frank;Moser, Leo (1966), "The theory of round robin tournaments",American Mathematical Monthly,73 (3):231–246,doi:10.2307/2315334,JSTOR 2315334.
• Havet, Frédéric (2013),"Section 3.1: Gallai–Roy Theorem and related results"(PDF),Orientations and colouring of graphs, Lecture notes for the summer school SGT 2013 in Oléron, France, pp. 15–19
• Landau, H.G. (1953), "On dominance relations and the structure of animal societies. III. The condition for a score structure",Bulletin of Mathematical Biophysics,15 (2):143–148,doi:10.1007/BF02476378.
• Laslier, J.-F. (1997),Tournament Solutions and Majority Voting, Springer
• McGarvey, David C. (1953), "A Theorem on the Construction of Voting Paradoxes",Econometrica,21 (4):608–610,doi:10.2307/1907926,JSTOR 1907926
• Moon, J. W. (1966),"On subtournaments of a tournament",Canadian Mathematical Bulletin,9 (3):297–301,doi:10.4153/CMB-1966-038-7.
• Rédei, László (1934), "Ein kombinatorischer Satz",Acta Litteraria Szeged,7:39–43.
• Reid, K.B.; Parker, E.T. (1970), "Disproof of a conjecture of Erdös and Moser",Journal of Combinatorial Theory,9 (3):225–238,doi:10.1016/S0021-9800(70)80061-8
• Stearns, Richard (1959), "The Voting Problem",The American Mathematical Monthly,66 (9):761–763,doi:10.2307/2310461,JSTOR 2310461
• Szekeres, E.;Szekeres, G. (1965), "On a problem of Schütte and Erdős",The Mathematical Gazette,49 (369):290–293,doi:10.2307/3612854,JSTOR 3612854,MR 0186566.
• Takács, Lajos (1991), "A Bernoulli Excursion and Its Various Applications",Advances in Applied Probability,23 (3), Applied Probability Trust:557–585,doi:10.2307/1427622,JSTOR 1427622.
• Thomassen, Carsten (1980), "Hamiltonian-Connected Tournaments",Journal of Combinatorial Theory, Series B,28 (2):142–163,doi:10.1016/0095-8956(80)90061-1.
• Yao, T.X. (1989), "On Reid conjecture of score sets for tournaments",Chinese Sci. Bull.,34:804–808.

This article incorporates material from tournament onPlanetMath, which is licensed under theCreative Commons Attribution/Share-Alike License.

• Directed graphs

• Articles with short description
• Short description is different from Wikidata
• CS1 French-language sources (fr)
• Wikipedia articles incorporating text from PlanetMath