Editing Tournament (graph theory)

{{Short description|Directed graph where each vertex pair has one arc}}
{{Infobox graph
 | name = Tournament
 | image = [[Image:4-tournament.svg|180px]]
 | image_caption = A tournament on 4 vertices
 | vertices = <math>n</math>
 | edges = <math>\binom{n}{2}</math>
}}
In [[graph theory]], a '''tournament''' is a [[directed graph]] with exactly one edge between each two [[vertex (graph theory)|vertices]], in one of the two possible directions. Equivalently, a tournament is an [[Orientation (graph theory)|orientation]] of an [[complete graph|undirected complete graph]]. (However, as directed graphs, tournaments are not complete: complete directed graphs have two edges, in both directions, between each two vertices.<ref>{{mathworld |title=Tournament |id=Tournament|mode=cs2}}</ref>) Equivalently, a tournament is a [[Connected_relation|complete]] [[Asymmetric_relation|asymmetric]] [[Binary_relation|relation]].<ref>{{cite journal |last1=Moulin |first1=Hervé |author-link1=Hervé Moulin |date=1986 |title=Choosing from a tournament |url=https://link.springer.com/article/10.1007/BF00292732 |journal=Social Choice and Welfare |volume=3 |issue=4 |pages=271–291 |doi=10.1007/BF00292732 |access-date=January 19, 2025 |quote=A tournament is any complete asymmetric relation over a finite set A of outcomes describing pairwise comparisons.}}</ref><ref>{{cite journal |last1=Laffond |first1=Gilbert |last2=Laslier |first2=Jean-Francois |last3=Le Breton |first3=Michel |date=January 1993 |title=The Bipartisan Set of a Tournament Game |url=https://www.sciencedirect.com/science/article/abs/pii/S0899825683710109 |journal=Games and Economic Behavior |volume=5 |issue=1 |pages=182–201 |doi=10.1006/game.1993.1010 |access-date=January 19, 2025 |quote=A tournament is a complete asymmetric binary relation U over a finite set X of outcomes.}}</ref>

The name ''tournament'' comes from interpreting the graph as the outcome of a [[round-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 by [[H. G. Landau]] in 1953 to model dominance relations in flocks of chickens.{{sfnp|Landau|1953}} Tournaments are also heavily studied in [[social choice theory|voting theory]], where they can represent partial information about voter preferences among multiple candidates, and are central to the definition of [[Condorcet methods]].

If every player beats the same number of other players ([[Copeland score|indegree − outdegree]] = 0) the tournament is called ''regular''.

== Paths and cycles ==
[[Image:Tournament Hamiltonian path.svg|thumb|{{mvar|a}} is inserted between {{math|''v''{{sub|2}}}} and {{math|''v''{{sub|3}}}}.]]
Any tournament on a [[finite set|finite]] number <math>n</math> of vertices contains a [[Hamiltonian path]], i.e., directed path on all <math>n</math> vertices ([[László Rédei|Rédei]] 1934).

This is easily shown by [[Mathematical induction|induction]] on <math>n</math>: suppose that the statement holds for <math>n</math>, and consider any tournament <math>T</math> on <math>n+1</math> vertices. Choose a vertex <math>v_0</math> of <math>T</math> and consider a directed path <math>v_1,v_2,\ldots,v_n</math> in <math>T\smallsetminus \{v_0\}</math>. There is some <math>i \in \{0,\ldots,n\}</math> such that <math>(i=0 \vee v_i \rightarrow v_0) \wedge (v_0 \rightarrow v_{i+1} \vee i=n)</math>. (One possibility is to let <math>i \in \{0,\ldots,n\}</math> be maximal such that for every <math>j \leq i, v_j \rightarrow v_0</math>. Alternatively, let <math>i</math> be minimal such that <math>\forall j > i, v_0 \rightarrow v_j</math>.)
<math display="block">v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n</math>
is a directed path as desired. This argument also gives an algorithm for finding the Hamiltonian path. More efficient algorithms,  that require examining only <math>O(n \log n)</math> of the edges, are known. The Hamiltonian paths are in one-to-one correspondence with the minimal [[feedback arc set]]s of the tournament.{{sfnp|Bar-Noy|Naor|1990}} Rédei's theorem is the special case for complete graphs of the [[Gallai–Hasse–Roy–Vitaver theorem]], relating the lengths of paths in orientations of graphs to the [[chromatic number]] of these graphs.{{sfnp|Havet|2013}}

Another basic result on tournaments is that every [[strongly connected component|strongly connected]] tournament has a [[Hamiltonian cycle]].{{sfnp|Camion|1959}} More strongly, every strongly connected tournament is [[pancyclic graph|vertex pancyclic]]: for each vertex <math>v</math>, and each <math>k</math> in the range from three to the number of vertices in the tournament, there is a cycle of length <math>k</math> containing <math>v</math>.{{sfnp|Moon|1966|loc=Theorem 1}} A tournament <math>T</math> is <math>k</math>-strongly connected if for every set <math>U</math> of <math>k-1</math> vertices of <math>T</math>, <math>T-U</math> is strongly connected. 
If the tournament is 4‑strongly connected, then each pair of vertices can be connected with a Hamiltonian path.{{sfnp|Thomassen|1980}} For every set <math>B</math> of at most <math>k-1</math> arcs of a <math>k</math>-strongly connected tournament <math>T</math>, we have that <math>T-B</math> has a Hamiltonian cycle.{{sfnp|Fraisse|Thomassen|1987}} This result was extended by {{harvtxt|Bang-Jensen|Gutin|Yeo|1997}}.{{sfnp|Bang-Jensen|Gutin|Yeo|1997}}

== Transitivity ==
[[Image:8-tournament-transitive.svg|thumb|240px|A transitive tournament on 8 vertices.]]

A tournament in which <math>((a \rightarrow b)</math> and <math>(b \rightarrow c))</math> <math>\Rightarrow</math> <math>(a \rightarrow c)</math> is called '''transitive'''. In other words, in a transitive tournament, the vertices may be (strictly) [[total order|totally ordered]] by the edge relation, and the edge relation is the same as [[reachability]].

===Equivalent conditions===
The following statements are equivalent for a tournament <math>T</math> on <math>n</math> vertices:

# <math>T</math> is transitive.
# <math>T</math> is a strict total ordering.
# <math>T</math> is [[directed acyclic graph|acyclic]].
# <math>T</math> does not contain a cycle of length 3.
# The score sequence (set of outdegrees) of <math>T</math> is <math>\{0,1,2,\ldots,n-1\}</math>.
# <math>T</math> has exactly one Hamiltonian path.

===Ramsey theory===
Transitive tournaments play a role in [[Ramsey theory]] analogous to that of [[clique (graph theory)|cliques]] in undirected graphs. In particular, every tournament on <math>n</math> vertices contains a transitive subtournament on <math>1+\lfloor\log_2 n\rfloor</math> vertices. The proof is simple: choose any one vertex <math>v</math> to be part of this subtournament, and form the rest of the subtournament recursively on either the set of incoming neighbors of <math>v</math> or the set of outgoing neighbors of <math>v</math>, whichever is larger. For instance, every tournament on seven vertices contains a three-vertex transitive subtournament; the [[Paley graph|Paley tournament]] on seven vertices shows that this is the most that can be guaranteed.{{sfnp|Erdős|Moser|1964}} However, {{harvtxt|Reid|Parker|1970}} showed that this bound is not tight for some larger values of&nbsp;<math>n</math>.{{sfnp|Reid|Parker|1970}}

{{harvtxt|Erdős|Moser|1964}} proved that there are tournaments on <math>n</math> vertices without a transitive subtournament of size <math>2+2\lfloor\log_2 n\rfloor</math> Their proof uses a [[Combinatorial proof|counting argument]]: the number of ways that a <math>k</math>-element transitive tournament can occur as a subtournament of a larger tournament on <math>n</math> labeled vertices is
<math display="block">\binom{n}{k}k!2^{\binom{n}{2}-\binom{k}{2}},</math>
and when <math>k</math> is larger than <math>2+2\lfloor\log_2 n\rfloor</math>, this number is too small to allow for an occurrence of a transitive tournament within each of the <math>2^{\binom{n}{2}}</math> different tournaments on the same set of <math>n</math> labeled vertices.{{sfnp|Erdős|Moser|1964}}

===Paradoxical tournaments===
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 <math>T=(V,E)</math> is called <math>k</math>-paradoxical if for every <math>k</math>-element subset <math>S</math> of <math>V</math> there is a vertex <math>v_0</math> in <math>V\setminus S</math> such that <math>v_0 \rightarrow v</math> for all <math>v \in S</math>. By means of the [[probabilistic method]], [[Paul Erdős]] showed that for any fixed value of <math>k</math>, if <math>|V| \geq k^22^k\ln(2+o(1))</math>, then almost every tournament on <math>V</math> is <math>k</math>-paradoxical.<ref>{{harvtxt|Erdős|1963}}</ref> On the other hand, an easy argument shows that any <math>k</math>-paradoxical tournament must have at least <math>2^{k+1}-1</math> players, which was improved to <math>(k+2)2^{k-1}-1</math> by [[Esther Szekeres|Esther]] and [[George Szekeres]] in 1965.{{sfnp|Szekeres|Szekeres|1965}} There is an explicit construction of <math>k</math>-paradoxical tournaments with <math>k^24^{k-1}(1+o(1))</math> players by [[Ronald Graham|Graham]] and Spencer (1971) namely the [[Paley tournament]].

===Condensation===
The [[Condensation (graph theory)|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.<ref>{{harvtxt|Harary|Moser|1966}}, Corollary 5b.</ref>

==Score sequences and score sets==
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 <math>(s_1, s_2, \ldots, s_n)</math> is a score sequence if and only if:{{sfnp|Landau|1953}}
# <math>0 \le s_1 \le s_2 \le \cdots \le s_n</math>
# <math>s_1 + s_2 + \cdots + s_i \ge {i \choose 2}, \text{ for }i = 1, 2, \ldots, n - 1</math>
# <math>s_1 + s_2 + \cdots + s_n = {n \choose 2}.</math>

Let <math>s(n)</math> be the number of different score sequences of size <math>n</math>. The sequence <math>s(n)</math> {{OEIS|id=A000571}} 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'':
:<math>s(n) > c_1 4^n n^{-5/2},</math>
where <math>c_1 = 0.049.</math>
Takács later showed, using some reasonable but unproven assumptions, that
:<math>s(n) < c_2 4^n n^{-5/2},</math>
where <math>c_2 < 4.858.</math>{{sfnp|Takács|1991}}

Together these provide evidence that:
:<math>s(n) \in \Theta (4^n n^{-5/2}).</math>

Here <math>\Theta</math> signifies an [[Big O notation#Related asymptotic notations|asymptotically tight bound]].

Yao showed that every nonempty set of nonnegative integers is the score set for some tournament.{{sfnp|Yao|1989}}

== Majority relations ==
In [[social choice theory]], tournaments naturally arise as majority relations of preference profiles.{{sfnp|Brandt|Brill|Harrenstein|2016}} Let <math>A</math> be a finite set of alternatives, and consider a list <math>P = (\succ_1, \dots, \succ_n)</math> of [[linear order]]s over <math>A</math>. We interpret each order <math>\succ_i</math> as the [[preference relation|preference ranking]] of a voter <math>i</math>. The (strict) majority relation <math>\succ_{\text{maj}}</math> of <math>P</math> over <math>A</math> is then defined so that <math>a \succ_{\text{maj}} b</math> if and only if a majority of the voters prefer <math>a</math> to <math>b</math>, that is <math>|\{ i \in [n] : a \succ_i b \}| > |\{ i \in [n] : b \succ_i a \}|</math>. If the number <math>n</math> of voters is odd, then the majority relation forms the dominance relation of a tournament on vertex set <math>A</math>.

By a lemma of McGarvey, every tournament on <math>m</math> vertices can be obtained as the majority relation of at most <math>m(m-1)</math> voters.<ref>{{harvtxt|McGarvey|1953}}; {{harvtxt|Brandt|Brill|Harrenstein|2016}}</ref> Results by [[Richard E. Stearns|Stearns]] and Erdős & Moser later established that <math>\Theta(m/\log m)</math> voters are needed to induce every tournament on <math>m</math> vertices.<ref>{{harvtxt|Stearns|1959}}; {{harvtxt|Erdős|Moser|1964}}</ref>

Laslier (1997) studies in what sense a set of vertices can be called the set of "winners" of a tournament.{{sfnp|Laslier|1997}} 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.{{sfnp|Austen-Smith|Banks|1999}}

== See also ==
* [[Oriented graph]]
* [[Paley tournament]]
* [[Sumner's conjecture]]
* [[Tournament solution]]

==Notes==
{{Reflist}}

== References ==
*{{citation|last1=Austen-Smith|first1=D.|first2=J.|last2=Banks|title=Positive Political theory|year=1999|publisher=University of Michigan Press}}
*{{citation
 | last1 = Bang-Jensen | first1 = J. 
 | last2 = Gutin | first2 = G. | author2-link = Gregory Gutin
 | last3 = Yeo | first3 = A. 
 | journal = Combinatorics, Probability and Computing
 | pages = 255–261
 | title = Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments
 | volume = 6
 | year = 1997| issue = 3 
 | doi = 10.1017/S0963548397003027 
 }}
*{{citation|doi=10.1137/0403002|first1=A.|last1=Bar-Noy|first2=J.|last2=Naor|author2-link=Joseph Seffi Naor|title=Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments|journal=[[SIAM Journal on Discrete Mathematics]]|volume=3|issue=1|pages=7–20|year=1990}}
*{{citation|last1=Brandt|first1=Felix|last2=Brill|first2=Markus|last3=Harrenstein|first3=Paul|contribution=Chapter 3: Tournament Solutions|title=Handbook of Computational Social Choice |editor1-last=Brandt|editor1-first=Felix|editor2-last=Conitzer|editor2-first=Vincent|editor3-last=Endriss|editor3-first=Ulle|editor4-last=Lang|editor4-first=Jérôme|editor5-last=Procaccia|editor5-first=Ariel D.|publisher=Cambridge University Press|year=2016|isbn=9781107060432}}
* {{Citation | first=Paul | last=Camion
| title=Chemins et circuits hamiltoniens des graphes complets 
| journal=[[Comptes Rendus de l'Académie des Sciences de Paris]]
| url = https://gallica.bnf.fr/ark:/12148/bpt6k731d/f1025.item
| language = French
| volume=249 | year=1959 | pages=2151&ndash;2152 }}
*{{citation
 | last = Erdős | first = P. | author1-link = Paul Erdős
 | journal = [[The Mathematical Gazette]]
 | jstor = 3613396
 | mr = 0159319
 | pages = 220–223
 | title = On a problem in graph theory
 | url = http://www.renyi.hu/~p_erdos/1963-08.pdf
 | volume = 47
 | year = 1963| issue = 361 | doi = 10.2307/3613396 }}
*{{citation
 | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
 | last2 = Moser | first2 = L. | author2-link = Leo Moser
 | journal = Magyar Tud. Akad. Mat. Kutató Int. Közl.
 | mr = 0168494
 | pages = 125–132
 | title = On the representation of directed graphs as unions of orderings
 | url = http://www.renyi.hu/~p_erdos/1964-22.pdf
 | volume = 9
 | year = 1964}}
*{{citation
 | last1 = Fraisse | first1 = P. 
 | last2 = Thomassen | first2 = C. 
 | journal = [[Graphs and Combinatorics]]
 | pages = 239–250
 | title = A constructive solution to a tournament problem
 | volume = 3
 | year = 1987 | doi = 10.1007/BF01788546 
 }}.
*{{citation
 | last1 = Graham | first1 = R. L. | author1-link = Ronald Graham
 | last2 = Spencer | first2 = J. H. | author2-link = Joel Spencer
 | journal = [[Canadian Mathematical Bulletin]]
 | mr = 0292715
 | pages = 45–48
 | title = A constructive solution to a tournament problem
 | volume = 14
 | year = 1971 | doi=10.4153/cmb-1971-007-1}}.
*{{citation
 | last1 = Harary | first1 = Frank | author1-link = Frank Harary
 | last2 = Moser | first2 = Leo | author2-link = Leo Moser
 | doi = 10.2307/2315334
 | issue = 3
 | journal = [[American Mathematical Monthly]]
 | pages = 231–246
 | title = The theory of round robin tournaments
 | volume = 73
 | year = 1966
 | jstor = 2315334}}.
*{{citation
 | last = Havet | first = Frédéric
 | contribution = Section 3.1: Gallai–Roy Theorem and related results
 | contribution-url = https://oc.g-scop.grenoble-inp.fr/conf/sgt2013/oleron.pdf
 | pages = 15–19
 | series = Lecture notes for the summer school SGT 2013 in Oléron, France
 | title = Orientations and colouring of graphs
 | year = 2013}}
* {{Citation | first=H.G. | last=Landau | title=On dominance relations and the structure of animal societies. III. The condition for a score structure | journal=[[Bulletin of Mathematical Biophysics]] | volume=15 | issue=2 | pages=143–148 | year=1953 | doi=10.1007/BF02476378}}.
*{{citation
 | last = Laslier | first = J.-F.
 | title = Tournament Solutions and Majority Voting
 | publisher = Springer
 | year = 1997}}
*{{citation|last=McGarvey|first=David C.|year=1953|title=A Theorem on the Construction of Voting Paradoxes|jstor=1907926|journal=Econometrica|volume=21|issue=4|pages=608–610|doi=10.2307/1907926}}
*{{citation
 | doi = 10.4153/CMB-1966-038-7
 | last = Moon | first = J. W.
 | issue = 3
 | journal = [[Canadian Mathematical Bulletin]]
 | pages = 297–301
 | title = On subtournaments of a tournament
 | url = http://cms.math.ca/cmb/v9/p297
 | volume = 9
 | year = 1966| doi-access = free
 }}.
* {{Citation | first=László | last=Rédei | authorlink = László Rédei
| title=Ein kombinatorischer Satz | journal=Acta Litteraria Szeged | volume=7 
| year=1934 | pages=39&ndash;43 }}.
* {{Citation | first1=K.B. | last1=Reid |first2=E.T. | last2=Parker
| title=Disproof of a conjecture of Erdös and Moser | journal=[[Journal of Combinatorial Theory]] | volume=9 | issue=3 | doi=10.1016/S0021-9800(70)80061-8
| year=1970 | pages=225&ndash;238 | doi-access=free }}
*{{citation|last=Stearns|first=Richard|year=1959|title=The Voting Problem|jstor=2310461|journal=The American Mathematical Monthly|volume=66|issue=9|pages=761–763|doi=10.2307/2310461}}
*{{citation
 | last1 = Szekeres | first1 = E. | author1-link = Esther Szekeres
 | last2 = Szekeres | first2 = G. | author2-link = George Szekeres
 | journal = [[The Mathematical Gazette]]
 | mr = 0186566
 | pages = 290–293
 | title = On a problem of Schütte and Erdős
 | volume = 49
 | year = 1965 | issue = 369 | doi=10.2307/3612854| jstor = 3612854 }}.
*{{Citation | title=A Bernoulli Excursion and Its Various Applications | journal=Advances in Applied Probability | year=1991|volume=23 | issue=3 | pages= 557–585 | doi=10.2307/1427622 | publisher=Applied Probability Trust | last=Takács | first=Lajos | authorlink = Lajos Takács | jstor=1427622}}.
* {{Citation | first1=Carsten | last1=Thomassen | authorlink = Carsten Thomassen (mathematician) | year=1980
| title=Hamiltonian-Connected Tournaments 
| journal=[[Journal of Combinatorial Theory]] | series = Series B | volume=28 | issue=2 | pages=142&ndash;163
| doi=10.1016/0095-8956(80)90061-1 | doi-access=free }}.
* {{Citation | first=T.X. | last=Yao | year=1989
| title=On Reid conjecture of score sets for tournaments 
| journal=Chinese Sci. Bull.  | volume=34 | pages=804&ndash;808 }}.

{{PlanetMath attribution|id=3518|title=tournament}}
{{Authority control}}

{{DEFAULTSORT:Tournament (Graph Theory)}}
[[Category:Directed graphs]]