Tournament (graph theory)

Template:Short description Template:Infobox graph In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an 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>Template:Mathworld</ref>) Equivalently, a tournament is a complete asymmetric relation.<ref>Template:Cite journal</ref><ref>Template:Cite journal</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.Template:Sfnp Tournaments are also heavily studied in 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 (indegree − outdegree = 0) the tournament is called regular.

Paths and cyclesEdit

File:Tournament Hamiltonian path.svg

Template:Mvar is inserted between Template:Math and Template:Math.

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

This is easily shown by 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 sets of the tournament.Template:Sfnp 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.Template:Sfnp

Another basic result on tournaments is that every strongly connected tournament has a Hamiltonian cycle.Template:Sfnp More strongly, every strongly connected tournament is 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>.Template:Sfnp 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.Template:Sfnp 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.Template:Sfnp This result was extended by Template:Harvtxt.Template:Sfnp

TransitivityEdit

File:8-tournament-transitive.svg

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) 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 <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 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 theoryEdit

Transitive tournaments play a role in Ramsey theory analogous to that of 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 tournament on seven vertices shows that this is the most that can be guaranteed.Template:Sfnp However, Template:Harvtxt showed that this bound is not tight for some larger values of <math>n</math>.Template:Sfnp

Template:Harvtxt 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 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.Template:Sfnp

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 <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>Template:Harvtxt</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 and George Szekeres in 1965.Template:Sfnp There is an explicit construction of <math>k</math>-paradoxical tournaments with <math>k^24^{k-1}(1+o(1))</math> 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.<ref>Template:Harvtxt, Corollary 5b.</ref>

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 <math>(s_1, s_2, \ldots, s_n)</math> is a score sequence if and only if:Template:Sfnp

<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> (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 <math>c_1 = 0.049.</math> Takács later showed, using some reasonable but unproven assumptions, that

where <math>c_2 < 4.858.</math>Template:Sfnp

Together these provide evidence that:

<math>s(n) \in \Theta (4^n n^{-5/2}).</math>

Here <math>\Theta</math> signifies an asymptotically tight bound.

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

Majority relationsEdit

In social choice theory, tournaments naturally arise as majority relations of preference profiles.Template:Sfnp Let <math>A</math> be a finite set of alternatives, and consider a list <math>P = (\succ_1, \dots, \succ_n)</math> of linear orders over <math>A</math>. We interpret each order <math>\succ_i</math> as the 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>Template:Harvtxt; Template:Harvtxt</ref> Results by 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>Template:Harvtxt; Template:Harvtxt</ref>

Laslier (1997) studies in what sense a set of vertices can be called the set of "winners" of a tournament.Template:Sfnp 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.Template:Sfnp

NotesEdit

Template:Reflist

ReferencesEdit

{{#if: | This article incorporates material from the following PlanetMath articles, which are licensed under the Creative Commons Attribution/Share-Alike License: {{#if: | tournament | {{#if: 3518 | tournament | [{{{sourceurl}}} tournament] }} }}, {{#if: | {{{title2}}} | {{#if: | {{{title2}}} | [{{{sourceurl2}}} {{{title2}}}] }} }}{{#if: | , {{#if: | {{{title3}}} | {{#if: | {{{title3}}} | [{{{sourceurl3}}} {{{title3}}}] }} }} }}{{#if: | , {{#if: | {{{title4}}} | {{#if: | {{{title4}}} | [{{{sourceurl4}}} {{{title4}}}] }} }} }}{{#if: | , {{#if: | {{{title5}}} | {{#if: | {{{title5}}} | [{{{sourceurl5}}} {{{title5}}}] }} }} }}{{#if: | , {{#if: | {{{title6}}} | {{#if: | {{{title6}}} | [{{{sourceurl6}}} {{{title6}}}] }} }} }}{{#if: | , {{#if: | {{{title7}}} | {{#if: | {{{title7}}} | [{{{sourceurl7}}} {{{title7}}}] }} }} }}{{#if: | , {{#if: | {{{title8}}} | {{#if: | {{{title8}}} | [{{{sourceurl8}}} {{{title8}}}] }} }} }}{{#if: | , {{#if: | {{{title9}}} | {{#if: | {{{title9}}} | [{{{sourceurl9}}} {{{title9}}}] }} }} }}. | This article incorporates material from {{#if: | tournament | tournament}} on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. }} Template:Authority control