Tournament (graph theory)

Image:Tournament Hamiltonian path.svg

Any tournament on a finite number $n$ of vertices contains a Hamiltonian path, i.e., directed path on all $n$ vertices (Rédei 1934).

This is easily shown by induction on $n$: suppose that the statement holds for $n$, and consider any tournament $T$ on $n+1$ vertices. Choose a vertex $v\_0$ of $T$ and consider a directed path $v\_1,v\_2,\backslash ldots,v\_n$ in $T\backslash smallsetminus\; \backslash \{v\_0\backslash \}$. There is some $i\; \backslash in\; \backslash \{0,\backslash ldots,n\backslash \}$ such that $(i=0\; \backslash vee\; v\_i\; \backslash rightarrow\; v\_0)\; \backslash wedge\; (v\_0\; \backslash rightarrow\; v\_\{i+1\}\; \backslash vee\; i=n)$. (One possibility is to let $i\; \backslash in\; \backslash \{0,\backslash ldots,n\backslash \}$ be maximal such that for every $j\; \backslash leq\; i,\; v\_j\; \backslash rightarrow\; v\_0$. Alternatively, let $i$ be minimal such that $\backslash forall\; j\; >\; i,\; v\_0\; \backslash rightarrow\; v\_j$.)

$$v\_1,\backslash ldots,v\_i,v\_0,v\_\{i+1\},\backslash ldots,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 $O(n\; \backslash log\; n)$ of the edges, are known. The Hamiltonian paths are in one-to-one correspondence with the minimal feedback arc sets 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 tournament has a Hamiltonian cycle.{{sfnp|Camion|1959}} More strongly, every strongly connected tournament is vertex pancyclic: for each vertex $v$, and each $k$ in the range from three to the number of vertices in the tournament, there is a cycle of length $k$ containing $v$.{{sfnp|Moon|1966|loc=Theorem 1}} A tournament $T$ is $k$-strongly connected if for every set $U$ of $k-1$ vertices of $T$, $T-U$ 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 $B$ of at most $k-1$ arcs of a $k$-strongly connected tournament $T$, we have that $T-B$ 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}}

Image:8-tournament-transitive.svg

A tournament in which $((a\; \backslash rightarrow\; b)$ and $(b\; \backslash rightarrow\; c))$ $\backslash Rightarrow$ $(a\; \backslash rightarrow\; c)$ 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.

The following statements are equivalent for a tournament $T$ on $n$ vertices:

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

Transitive tournaments play a role in Ramsey theory analogous to that of cliques in undirected graphs. In particular, every tournament on $n$ vertices contains a transitive subtournament on $1+\backslash lfloor\backslash log\_2\; n\backslash rfloor$ vertices. The proof is simple: choose any one vertex $v$ to be part of this subtournament, and form the rest of the subtournament recursively on either the set of incoming neighbors of $v$ or the set of outgoing neighbors of $v$, 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.{{sfnp|Erdős|Moser|1964}} However, {{harvtxt|Reid|Parker|1970}} showed that this bound is not tight for some larger values of $n$.{{sfnp|Reid|Parker|1970}}

{{harvtxt|Erdős|Moser|1964}} proved that there are tournaments on $n$ vertices without a transitive subtournament of size $2+2\backslash lfloor\backslash log\_2\; n\backslash rfloor$ Their proof uses a counting argument: the number of ways that a $k$-element transitive tournament can occur as a subtournament of a larger tournament on $n$ labeled vertices is

$$\backslash binom\{n\}\{k\}k!2^\{\backslash binom\{n\}\{2\}-\backslash binom\{k\}\{2\}\},$$

and when $k$ is larger than $2+2\backslash lfloor\backslash log\_2\; n\backslash rfloor$, this number is too small to allow for an occurrence of a transitive tournament within each of the $2^\{\backslash binom\{n\}\{2\}\}$ different tournaments on the same set of $n$ labeled vertices.{{sfnp|Erdős|Moser|1964}}

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

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.{{harvtxt|Harary|Moser|1966}}, Corollary 5b.

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 $(s\_1,\; s\_2,\; \backslash ldots,\; s\_n)$ is a score sequence if and only if:{{sfnp|Landau|1953}}

1. $0\; \backslash le\; s\_1\; \backslash le\; s\_2\; \backslash le\; \backslash cdots\; \backslash le\; s\_n$
2. $s\_1\; +\; s\_2\; +\; \backslash cdots\; +\; s\_i\; \backslash ge\; \{i\; \backslash choose\; 2\},\; \backslash text\{\; for\; \}i\; =\; 1,\; 2,\; \backslash ldots,\; n\; -\; 1$
3. $s\_1\; +\; s\_2\; +\; \backslash cdots\; +\; s\_n\; =\; \{n\; \backslash choose\; 2\}.$

Let $s(n)$ be the number of different score sequences of size $n$. The sequence $s(n)$ {{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:

:$s(n)\; >\; c\_1\; 4^n\; n^\{-5/2\},$

where $c\_1\; =\; 0.049.$

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

:

where {{sfnp|Takács|1991}}

Together these provide evidence that:

:$s(n)\; \backslash in\; \backslash Theta\; (4^n\; n^\{-5/2\}).$

Here $\backslash Theta$ signifies an asymptotically tight bound.

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

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

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

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}}

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

{{Reflist}}

• {{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–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–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–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–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–808 }}.

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

{{Authority control}}

{{DEFAULTSORT:Tournament (Graph Theory)}}

Category:Directed graphs