Tournament (graph theory)

Tournament
A tournament on 4 vertices
Vertices	n
Edges	$\binom{n}{2}$
v · directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge. Many of the important properties of tournaments were first investigated by Landau in order to model dominance relations in flocks of chickens. Current applications of tournaments include the study of voting theory and social choice theory among other things. The name tournament originates from such a graph's interpretation as the outcome of a round-robin tournament in which every player encounters every other player exactly once, and in which no draws occur. In the tournament digraph, the vertices correspond to the players. The edge between each pair of players is oriented from the winner to the loser. If player a beats player b, then it is said that a dominates b. Paths and cycles 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 v0 of T and consider a directed path $v_1,v_2,\ldots,v_n$ in $T\setminus \{v_0\}$. Now let $i \in \{0,\ldots,n\}$ be maximal such that for every $j \leq i$ there is a directed edge from vj to v0. $v_1,\ldots,v_i,v_0,v_{i+1},\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 \log n)$ of the edges, are known .[1] This implies that a strongly connected tournament has a Hamiltonian cycle (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.[2] Moreover, if the tournament is 4‑connected, each pair of vertices can be connected with a Hamiltonian path (Thomassen 1980). Transitivity A transitive tournament on 8 vertices. A tournament in which $((a \rightarrow b)$ and $(b \rightarrow c))$ $\Rightarrow$ $(a \rightarrow c)$ is called transitive. The following statements are equivalent for a tournament T on n vertices: T is transitive T is acyclic T does not contain a cycle of length 3 The score sequence (set of outdegrees) of T is {0,1,2,...,n − 1}. T has exactly one Hamiltonian path. Every tournament on n vertices has a transitive subtournament on log2n vertices. Reid and Parker showed that this bound is not tight. Erdős and Moser have proved that there are tournaments on n vertices without a transitive subtournament of size 2log2n. A player who wins all games would naturally be the tournament's winner. However, as the above example shows, there might 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 v0 in $V\setminus S$ such that $v_0 \rightarrow v$ for all $v \in S$. By means of the probabilistic method, Paul Erdős showed that for any fixed value of k, if |V| ≥ k22kln(2 + o(1)), then almost every tournament on V is k-paradoxical.[3] On the other hand, an easy argument shows that any k-paradoxical tournament must have at least 2k+1 − 1 players, which was improved to (k + 2)2k−1 − 1 by Esther and George Szekeres.[4] There is an explicit construction of k-paradoxical tournaments with k24k−1(1 + o(1)) players by Graham and Spencer,[5] namely the Paley tournament. The condensation of any tournament is itself a transitive tournament.[6] 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 $(s_1, s_2, \cdots, s_n)$ is a score sequence if and only if : $0 \le s_1 \le s_2 \le \cdots \le s_n$ $s_1 + s_2 + \cdots + s_i \ge {i \choose 2}, \mbox{for }i = 1, 2, \cdots, n - 1$ $s_1 + s_2 + \cdots + s_n = {n \choose 2}$ Let s(n) be the number of different score sequences of size n. The sequence s(n) (sequence A000571 in 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: $s(n) > c_1 4^n n^{-{5 \over 2}},$ where c1 = 0.049. Takács later showed, using some reasonable but unproven assumptions, that $s(n) < c_2 4^n n^{-{5 \over 2}},$ where c2 < 4.858. Together these provide evidence that: $s(n) \in \Theta (4^n n^{-{5 \over 2}}).$ Here Θ signifies an asymptotically tight bound. Yao showed that every nonempty set of nonnegative integers is the score set for some tournament. See also Oriented graph Paley tournament Stockmeyer tournament Sumner's conjecture Footnotes ^ 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 . ^ Moon (1966), Theorem 1. ^ Paul Erdős, On a problem in graph theory, Mathematical Gazette 47 (1963), no. 361, pp. 220–223. ^ Esther Szekeres and George Szekeres, On a problem of Schütte and Erdös, Mathematical Gazette 49 (1965), no. 369, pp. 290–293. ^ Ronald Graham and Joel H. Spencer, A construction to a tournament problem. Can Math Bull 14(1):45-48 (1971) ^ Harary & Moser (1966), Corollary 5b. References Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged 7: 39–43 . Camion, Paul (1959), "Chemins et circuits hamiltoniens des graphes complets", Comptes Rendus de l'Académie des Sciences de Paris 249: 2151–2152 . Harary, Frank; Moser, Leo (1966), "The theory of round robin tournaments", American Mathematical Monthly 73 (3): 231–246, doi:10.2307/2315334, JSTOR 2315334 . Moon, J. W. (1966), "On subtournaments of a tournament", Canadian Mathematical Bulletin 9 (3): 297–301, doi:10.4153/CMB-1966-038-7, http://cms.math.ca/cmb/v9/p297 . 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 . Takács, Lajos; Takacs, Lajos (1991), "A Bernoulli Excursion and Its Various Applications", Advances in Applied Probability (Applied Probability Trust) 23 (3): 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 . 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 . This article incorporates material from tournament on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. Wikimedia Foundation. 2010. Игры ⚽ Поможем написать реферат Self-addressed stamped envelope Stephanius Look at other dictionaries: Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia Tournament (disambiguation) — A tournament is a form of organized competition.Tournament may also refer to:In competition and games: * Tournament (medieval), a chivalrous competition of the Middle Ages * Tournament (solitaire), a solitaire card gameIn film and television: *… …   Wikipedia Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia Round-robin tournament — A round robin tournament (or all play all tournament) is a competition in which each contestant meets all other contestants in turn .[1] Contents 1 Terminology 2 Use 3 Evaluation …   Wikipedia Directed graph — A directed graph. A directed graph or digraph is a pair G = (V,A) (sometimes G = (V,E)) of:[1] a set V, whose elements are called vertices or …   Wikipedia Paley graph — infobox graph name = Paley graph image caption = The Paley graph of order 13 namesake = Raymond Paley vertices = edges = chromatic number = chromatic index = properties = Strongly regularIn mathematics, and specifically graph theory, Paley graphs …   Wikipedia Complete graph — K7, a complete graph with 7 vertices Vertices n Edges …   Wikipedia List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia Combinatoire probabiliste — Méthode probabiliste Cet article n est pas sur les systèmes de preuve interactive qui sont utilisés pour convaincre un vérificateur qu une démonstration est correcte, ni sur les algorithmes probabilistes, qui donnent la bonne réponse avec une… …   Wikipédia en Français Méthode probabiliste — Cet article n est pas sur les systèmes de preuve interactive qui sont utilisés pour convaincre un vérificateur qu une démonstration est correcte, ni sur les algorithmes probabilistes, qui donnent la bonne réponse avec une grande probabilité, mais …   Wikipédia en Français 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”