Tournament | |
---|---|
Vertices | |
Edges | |
Table of graphs and parameters |
A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is an orientation of a complete graph, or equivalently a directed graph in which every pair of distinct vertices is connected by a directed edge (often, called an arc) with any one of the two possible orientations.
Many of the important properties of tournaments were first investigated by H. G. Landau in Landau (1953) 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 beats player , then it is said that dominates. If every player beats the same number of other players (indegree = outdegree), the tournament is called regular.
Theorem — Any tournament on a finite number of vertices contains a Hamiltonian path, i.e., directed path on all vertices (Rédei 1934).
This is easily shown by induction on : suppose that the statement holds for , and consider any tournament on vertices. Choose a vertex of and consider a directed path in . There is some such that . (One possibility is to let be maximal such that for every . Alternatively, let be minimal such that .)
is a directed path as desired. This argument also gives an algorithm for finding the Hamiltonian path. More efficient algorithms, that require examining only of the edges, are known. The Hamiltonian paths are in one-to-one correspondence with the minimal feedback arc sets of the tournament. [1] 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. [2]
Another basic result on tournaments is that every strongly connected tournament has a Hamiltonian cycle. [3] More strongly, every strongly connected tournament is vertex pancyclic: for each vertex , and each in the range from three to the number of vertices in the tournament, there is a cycle of length containing . [4] A tournament is -strongly connected if for every set of vertices of , is strongly connected. If the tournament is 4‑strongly connected, then each pair of vertices can be connected with a Hamiltonian path. [5] For every set of at most arcs of a -strongly connected tournament , we have that has a Hamiltonian cycle. [6] This result was extended by Bang-Jensen, Gutin & Yeo (1997).
A tournament in which and 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 on vertices:
Transitive tournaments play a role in Ramsey theory analogous to that of cliques in undirected graphs. In particular, every tournament on vertices contains a transitive subtournament on vertices. [7] The proof is simple: choose any one vertex to be part of this subtournament, and form the rest of the subtournament recursively on either the set of incoming neighbors of or the set of outgoing neighbors of , 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 ( Erdős & Moser 1964 ). However, Reid & Parker (1970) showed that this bound is not tight for some larger values of .
Erdős & Moser (1964) proved that there are tournaments on vertices without a transitive subtournament of size Their proof uses a counting argument: the number of ways that a -element transitive tournament can occur as a subtournament of a larger tournament on labeled vertices is
and when is larger than , this number is too small to allow for an occurrence of a transitive tournament within each of the different tournaments on the same set of labeled vertices.
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 is called -paradoxical if for every -element subset of there is a vertex in such that for all . By means of the probabilistic method, Paul Erdős showed that for any fixed value of , if , then almost every tournament on is -paradoxical. [8] On the other hand, an easy argument shows that any -paradoxical tournament must have at least players, which was improved to by Esther and George Szekeres (1965). [9] There is an explicit construction of -paradoxical tournaments with 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. [10]
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 is a score sequence if and only if :
Let be the number of different score sequences of size . The sequence (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 Takács later showed, using some reasonable but unproven assumptions, that
where
Together these provide evidence that:
Here signifies an asymptotically tight bound.
Yao showed that every nonempty set of nonnegative integers is the score set for some tournament.
In social choice theory, tournaments naturally arise as majority relations of preference profiles. [11] Let be a finite set of alternatives, and consider a list of linear orders over . We interpret each order as the preference ranking of a voter . The (strict) majority relation of over is then defined so that if and only if a majority of the voters prefer to , that is . If the number of voters is odd, then the majority relation forms the dominance relation of a tournament on vertex set .
By a lemma of McGarvey, every tournament on vertices can be obtained as the majority relation of at most voters. [11] [12] Results by Stearns and Erdős & Moser later established that voters are needed to induce every tournament on vertices. [13]
Laslier (1997) studies in what sense a set of vertices can be called the set of "winners" of a tournament. 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. [14]
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let r and s be any two positive integers. Ramsey's theorem states that there exists a least positive integer R(r, s) for which every blue-red edge colouring of the complete graph on R(r, s) vertices contains a blue clique on r vertices or a red clique on s vertices. (Here R(r, s) signifies an integer that depends on both r and s.)
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.
In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation , or widest paths between all pairs of vertices in a weighted graph.
In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.
In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties, and is a special case of the forbidden subgraph problem on the maximum number of edges in a graph that does not have a given subgraph.
In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.
In graph theory, the Kneser graphK(n, k) is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.
In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex can reach a vertex if there exists a sequence of adjacent vertices which starts with and ends with .
Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph are the -element subsets of an -element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains -elements. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson.
In graph theory, a circulant graph is an undirected graph acted on by a cyclic group of symmetries which takes any vertex to any other vertex. It is sometimes called a cyclic graph, but this term has other meanings.
In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, relates two parameters of a graph:
In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal (1970).
In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized Petersen graph family was introduced in 1950 by H. S. M. Coxeter and was given its name in 1969 by Mark Watkins.
In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.
In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.
In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman.
In graph theory, a branch of mathematics, the Erdős–Hajnal conjecture states that families of graphs defined by forbidden induced subgraphs have either large cliques or large independent sets. It is named for Paul Erdős and András Hajnal.
In graph theory, the shortness exponent is a numerical parameter of a family of graphs that measures how far from Hamiltonian the graphs in the family can be. Intuitively, if is the shortness exponent of a graph family , then every -vertex graph in the family has a cycle of length near but some graphs do not have longer cycles. More precisely, for any ordering of the graphs in into a sequence , with defined to be the length of the longest cycle in graph , the shortness exponent is defined as
In graph theory, the graph removal lemma states that when a graph contains few copies of a given subgraph, then all of the copies can be eliminated by removing a small number of edges. The special case in which the subgraph is a triangle is known as the triangle removal lemma.
This article incorporates material from tournament on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.