Jump to content

Tournament (graph theory): Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Damelch (talk | contribs)
Damelch (talk | contribs)
Number of possible results: score sequence is a more common way of saying score vector
Line 43: Line 43:
# <math>s_1 + s_2 + \cdots + s_n = {n \choose 2}</math>
# <math>s_1 + s_2 + \cdots + s_n = {n \choose 2}</math>


Let <math>s(n)</math> be the number of different score vectors of size <math>n</math>. The sequence <math>s(n)</math> {{OEIS|id=A000571}} starts as:
Let <math>s(n)</math> be the number of different score sequence of size <math>n</math>. The sequence <math>s(n)</math> {{OEIS|id=A000571}} starts as:


1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...
1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

Revision as of 01:59, 9 December 2008

Tournament
A tournament on 4 vertices
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.

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 .

Paths and cycles

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 . Now let be maximal such that for all with . Then

is a directed path as desired.

A tournament on n vertices is strongly connected if and only if every vertex is on a cycle of length k for . This implies that a strongly connected tournament has a Hamiltonian cycle (Camion 1959). 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 and is called transitive. The following statements are equivalent for a tournament T on n vertices:

1. T is transitive

2. T is acyclic

3. The score sequence for a transitive tournament is {0,1,2,...,n-1}

4. T has exactly one hamiltonian path.

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 there isn't is called a -paradoxical tournament. More generally, a tournament is called -paradoxical if for every -subset of there is a such that for all . By means of the probabilistic method Paul Erdős showed that if is sufficiently large, then almost every tournament on is -paradoxical.

Number of possible results

Let us have competitors, and a scoring system where no ties are permitted. Let be the number of wins scored by competitor , and let us order them such that . Thus we define a score vector, , satisfying the following three conditions:

Let be the number of different score sequence 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, ...

It is possible to show that for sufficiently large n:

Also:

Where:

Together these show that:

Here signifies an asymptotically tight bound.

References

  • Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged, 7: 39–43{{citation}}: CS1 maint: extra punctuation (link) CS1 maint: multiple names: authors list (link)
  • Camion, Paul (1959), "Chemie et circuits hamiltoniens des graphes complets", Comptes Rendus de l'Académie des Sciences de Paris, 249: 2151–2152
  • Thomassen, Carsten (1980), "Hamiltonian-Connected Tournaments", Journal of Combinatorial Theory, Series B, 28: 142–163, doi:10.1016/0095-8956(80)90061-1
  • Takacs, Lajos (1991). "A Bernoulli Excursion and Its Various Applications". Advances in Applied Probability. 23 (3): 557–585. doi:10.2307/1427622.

tournament at PlanetMath.