Tournament (graph theory)

4-top tournament
peaks

n

{\ displaystyle n}

n

ribs:

{\binom {n}{2}}

{\ displaystyle {\ binom {n} {2}}}

{\ binom {n} {2}}

A tournament is a directed graph obtained from an undirected complete graph by assigning a direction to each edge. Thus, a tournament is a digraph in which each pair of vertices is connected by one directed arc.

Many important properties of tournaments were reviewed by Landau ^[1] in order to explore the model of chick dominance in a pack. Current tournament applications include research on voting and among other things. The name tournament comes from a graphical interpretation of the outcome of a round robin tournament in which each player encounters each other player exactly once, and in which there can be no one . In the tournament digraph, the peaks correspond to the players. The arc between each pair of players is oriented from the winner to the loser. If a player $a$ ${\ displaystyle a}$ $a$ defeats the player $b$ ${\ displaystyle b}$ $b$ then they say that $a$ ${\ displaystyle a}$ $a$ dominates $b$ ${\ displaystyle b}$ $b$ .

Content

Paths and Loops

Any tournament with a finite number $n$ ${\ displaystyle n}$ the vertices contains the Hamiltonian path , that is, the oriented path containing all $n$ ${\ displaystyle n}$ vertices ^[2] . This is easily shown by mathematical induction on $n$ ${\ displaystyle n}$ : let the statement be true for $n$ ${\ displaystyle n}$ , and let there be a certain tournament $T$ ${\ displaystyle T}$ with $n+1$ ${\ displaystyle n + 1}$ tops. Pick the top $v_{0}$ ${\ displaystyle v_ {0}}$ at $T$ ${\ displaystyle T}$ let it go $v_{1},v_{2},\ldots ,v_{n}$ ${\ displaystyle v_ {1}, v_ {2}, \ ldots, v_ {n}}$ - directional path to $T\setminus \{v_{0}\}$ ${\ displaystyle T \ setminus \ {v_ {0} \}}$ . Let be $i\in \{0,\ldots ,n\}$ ${\ displaystyle i \ in \ {0, \ ldots, n \}}$ - the maximum number is such that for any $j\leq i$ ${\ displaystyle j \ leq i}$ there is an arc from $v_{j}$ ${\ displaystyle v_ {j}}$ at $v_{0}$ ${\ displaystyle v_ {0}}$ . Then

v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}

{\ displaystyle v_ {1}, \ ldots, v_ {i}, v_ {0}, v_ {i + 1}, \ ldots, v_ {n}}

- the desired oriented path. This proof also gives the search algorithm for the Hamiltonian path. A more efficient algorithm is known that requires enumerating everything $\ O(n\log n)$ ${\ displaystyle \ O (n \ log n)}$ arcs ^[3] .

This means that a strictly connected tournament has a Hamiltonian cycle ^[4] . More strictly: any strongly connected tournament is vertex pancyclical - for any vertex v and for any k from three to the number of vertices in the tournament there is a cycle of length k containing v ^[5] . Moreover, if the tournament is 4-connected, any pair of vertices can be connected by the Hamiltonian path ^[6] .

Transitivity

Transitive tournament with 8 peaks.

Tournament in which $((a\rightarrow b)$ ${\ displaystyle ((a \ rightarrow b)}$ and $(b\rightarrow c))$ ${\ displaystyle (b \ rightarrow c))}$ $\Rightarrow$ ${\ displaystyle \ Rightarrow}$ $(a\rightarrow c)$ ${\ displaystyle (a \ rightarrow c)}$ is called transitive . In a transitive tournament, the vertices can be fully ordered in order of .

Equivalent conditions

The following statements for a tournament with n vertices are equivalent:

T is transitive.
T is acyclic .
T does not contain cycles of length 3.
The sequence of the number of wins (the set of semi-outcomes) T is {0,1,2, ..., n - 1}.
T contains exactly one Hamiltonian path.

Ramsey Theory

Transitive tournaments play a significant role in Ramsey theory , similar to the role that cliques play in undirected graphs. In particular, any tournament with n vertices contains a transitive sub-tournament with $1+\lfloor \log _{2}n\rfloor$ ${\ displaystyle 1+ \ lfloor \ log _ {2} n \ rfloor}$ vertices ^[7] . The proof is simple: we choose any vertex v as part of this sub-tournament and construct the sub-tournament recursively on the set of either the incoming neighbors of the vertex v or the set of outgoing neighbors, depending on which set is larger. For example, any seven-peak tournament contains a transitive three-peak tournament. The seven-peak Paley tournament shows that this is the maximum that can be guaranteed ^[7] . However, Reid and Parker ^[8] showed that this boundary is not strict for some large values of n .

Erdös and Moser ^[7] proved that there are tournaments with n vertices without transitive size sub-tournaments $2+2\lfloor \log _{2}n\rfloor$ ${\ displaystyle 2 + 2 \ lfloor \ log _ {2} n \ rfloor}$ . Their proof uses the : the number of options in which a transitive tournament with k vertices can be contained in a larger tournament with n marked vertices is

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

{\ displaystyle {\ binom {n} {k}} k! 2 ^ {{\ \ binom {n} {2}} - {\ binom {k} {2}}},}

and for k superior $2+2\lfloor \log _{2}n\rfloor$ ${\ displaystyle 2 + 2 \ lfloor \ log _ {2} n \ rfloor}$ this number is too small for a transitive tournament to be in each of $2^{\binom {n}{2}}$ ${\ displaystyle 2 ^ {\ binom {n} {2}}}$ different tournaments of the same set of n labeled peaks.

Paradoxical Tournaments

A player who wins all games will naturally be the winner of the tournament. However, as the existence of non-transitive tournaments shows, such a player may not be. A tournament in which each player loses at least one game is called a 1-paradox tournament. Generalizing, a tournament T = ( V , E ) is called k- paradoxical if, for any k -element subset S of V, there exists a vertex v ₀ in $V\setminus S$ ${\ displaystyle V \ setminus S}$ such that $v_{0}\rightarrow v$ ${\ displaystyle v_ {0} \ rightarrow v}$ for all $v\in S$ ${\ displaystyle v \ in S}$ . By means of the probabilistic method, Erdшos showed that for any fixed k under the condition | V | ≥ k ² 2 ^k ln (2 + o (1)) almost any tournament on V is k- paradoxical ^[9] . On the other hand, a simple argument shows that any k- paradox tournament should have at least 2 ^{k +1} - 1 players, which has been improved to ( k + 2) 2 ^{k −1} - 1 Esther and György Szekeres (1965) ^{[ 10]} . There is an explicit method for constructing k- paradoxical tournaments with k ² 4 ^{k −1} (1 + o (1)) players, developed by Graham and Spencer, namely, the Paley tournament ^[11] .

Condensation

any tournament is a transitive tournament. Thus, even if the tournament is not transitive, the strongly related components of the tournament can be completely ordered ^[12] .

Sequences of results and multiple results

The sequence of tournament results is a non-decreasing sequence of half-degrees of the outcome of the tournament peaks . The set of tournament results is the set of integers that are half-degrees of the outcome of the tournament tops.

Landau's theorem (1953) - a non-decreasing sequence of integers $(s_{1},s_{2},\cdots ,s_{n})$ ${\ displaystyle (s_ {1}, s_ {2}, \ cdots, s_ {n})}$ is a sequence of results if and only if:

$0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$ ${\ displaystyle 0 \ leq s_ {1} \ leq s_ {2} \ leq \ cdots \ leq s_ {n}}$
$s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},$ ${\ displaystyle s_ {1} + s_ {2} + \ cdots + s_ {i} \ geq {i \ choose 2},}$ for $i=1,2,\cdots ,n-1$ ${\ displaystyle i = 1,2, \ cdots, n-1}$
$s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.$ ${\ displaystyle s_ {1} + s_ {2} + \ cdots + s_ {n} = {n \ choose 2}.}$

Let be $s(n)$ ${\ displaystyle s (n)}$ - the number of different sequences of size results $n$ ${\ displaystyle n}$ . Sequence $s(n)$ ${\ displaystyle s (n)}$ begin with:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14 805 , 48 107 , ...

(sequence A000571 in OEIS )

Winston and Kleitman proved that for sufficiently large n

s(n)>c_{1}4^{n}n^{-{5 \over 2}},

{\ displaystyle s (n)> c_ {1} 4 ^ {n} n ^ {- {5 \ over 2}},}

Where $c_{1}=0.049.$ ${\ displaystyle c_ {1} = 0.049.}$ Takach later showed ^[13] using some plausible but unproven assumption that

s(n)<c_{2}4^{n}n^{-{5 \over 2}},

{\ displaystyle s (n) <c_ {2} 4 ^ {n} n ^ {- {5 \ over 2}},}

Where $c_{2}<4,858.$ ${\ displaystyle c_ {2} <4,858.}$

Together, this suggests that

s(n)\in \Theta (4^{n}n^{-{5 \over 2}}).

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

Here $\Theta$ ${\ displaystyle \ Theta}$ reflects an asymptotically strict boundary .

Yao showed ^[14] that any nonempty set of non-negative integers is the set of results for some tournament.

Notes

↑ HG Landau. On dominance relations and the structure of animal societies. III. The condition for a score structure // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , no. 2 . - S. 143-148 . - DOI : 10.1007 / BF02476378 .
↑ Lázló Rédei. Ein kombinatorischer Satz // Acta Litteraria Szeged. - 1934.- T. 7 . - S. 39-43 .
↑ A. Bar-Noy, J. Naor. Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments // SIAM Journal on Discrete Mathematics . - 1990. - T. 3 , no. 1 . - S. 7-20 . - DOI : 10.1137 / 0403002 .
↑ Chemins et circuits hamiltoniens des graphes complets // Comptes Rendus de l'Académie des Sciences de Paris. - 1959.- T. 249 . - S. 2151-2152 .
↑ JW Moon. On subtournaments of a tournament // Canadian Mathematical Bulletin. - 1966. - T. 9 , no. 3 . - S. 297-301 . - DOI : 10.4153 / CMB-1966-038-7 .
↑ Carsten Thomassen. Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Series B. - 1980.- T. 28 , no. 2 . - S. 142-163 . - DOI : 10.1016 / 0095-8956 (80) 90061-1 .
↑ ¹ ² ³ Paul Erdős, Leo Moser. On the representation of directed graphs as unions of orderings // Magyar Tud. Akad. Mat. Kutató Int. Közl. - 1964 .-- T. 9 . - S. 125-132 .
↑ KB Reid, ET Parker. Disproof of a conjecture of Erdös and Moser // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 3 . - S. 225—238 . - DOI : 10.1016 / S0021-9800 (70) 80061-8 .
↑ Paul Erdős. On a problem in graph theory // The Mathematical Gazette. - 1963.- T. 47 . - S. 220—223 .
↑ Esther Szekeres, George Szekeres. On a problem of Schütte and Erdős // The Mathematical Gazette. - 1965 .-- T. 49 . - S. 290-293 .
↑ Ronald Graham, Joel Spencer. A constructive solution to a tournament problem // Canadian Mathematical Bulletin. Bulletin Canadien de Mathématiques. - 1971. - T. 14 . - S. 45-48 .
↑ Frank Harary, Leo Moser. The theory of round robin tournaments // American Mathematical Monthly. - 1966. - T. 73 , no. 3 . - S. 231-246 . - DOI : 10.2307 / 2315334 .
↑ Lajos Takács. A Bernoulli Excursion and Its Various Applications // Advances in Applied Probability. - 1991. - T. 23 , no. 3 . - S. 557-585 . - DOI : 10.2307 / 1427622 .
↑ TX Yao. On Reid Conjecture Of Score Sets For Tournaments // Chinese Sci. Bull. - 1989 .-- T. 34 . - S. 804-808 .

[1] HG Landau. On dominance relations and the structure of animal societies. III. The condition for a score structure // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , no. 2 . - S. 143-148 . - DOI : 10.1007 / BF02476378 .

[2] Lázló Rédei. Ein kombinatorischer Satz // Acta Litteraria Szeged. - 1934.- T. 7 . - S. 39-43 .

[3] A. Bar-Noy, J. Naor. Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments // SIAM Journal on Discrete Mathematics . - 1990. - T. 3 , no. 1 . - S. 7-20 . - DOI : 10.1137 / 0403002 .

[4] Chemins et circuits hamiltoniens des graphes complets // Comptes Rendus de l'Académie des Sciences de Paris. - 1959.- T. 249 . - S. 2151-2152 .

[5] JW Moon. On subtournaments of a tournament // Canadian Mathematical Bulletin. - 1966. - T. 9 , no. 3 . - S. 297-301 . - DOI : 10.4153 / CMB-1966-038-7 .

[6] Carsten Thomassen. Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Series B. - 1980.- T. 28 , no. 2 . - S. 142-163 . - DOI : 10.1016 / 0095-8956 (80) 90061-1 .

[Moser-7] ¹ ² ³ Paul Erdős, Leo Moser. On the representation of directed graphs as unions of orderings // Magyar Tud. Akad. Mat. Kutató Int. Közl. - 1964 .-- T. 9 . - S. 125-132 .

[8] KB Reid, ET Parker. Disproof of a conjecture of Erdös and Moser // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 3 . - S. 225—238 . - DOI : 10.1016 / S0021-9800 (70) 80061-8 .

[9] Paul Erdős. On a problem in graph theory // The Mathematical Gazette. - 1963.- T. 47 . - S. 220—223 .

[10] Esther Szekeres, George Szekeres. On a problem of Schütte and Erdős // The Mathematical Gazette. - 1965 .-- T. 49 . - S. 290-293 .

[11] Ronald Graham, Joel Spencer. A constructive solution to a tournament problem // Canadian Mathematical Bulletin. Bulletin Canadien de Mathématiques. - 1971. - T. 14 . - S. 45-48 .

[12] Frank Harary, Leo Moser. The theory of round robin tournaments // American Mathematical Monthly. - 1966. - T. 73 , no. 3 . - S. 231-246 . - DOI : 10.2307 / 2315334 .

[13] Lajos Takács. A Bernoulli Excursion and Its Various Applications // Advances in Applied Probability. - 1991. - T. 23 , no. 3 . - S. 557-585 . - DOI : 10.2307 / 1427622 .

[14] TX Yao. On Reid Conjecture Of Score Sets For Tournaments // Chinese Sci. Bull. - 1989 .-- T. 34 . - S. 804-808 .