Editing Tournament (graph theory) (section)

== Transitivity ==
[[Image:8-tournament-transitive.svg|thumb|240px|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) [[total order|totally ordered]] by the edge relation, and the edge relation is the same as [[reachability]].

===Equivalent conditions===
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 [[directed acyclic graph|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 theory===
Transitive tournaments play a role in [[Ramsey theory]] analogous to that of [[clique (graph theory)|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 graph|Paley tournament]] on seven vertices shows that this is the most that can be guaranteed.{{sfnp|Erdős|Moser|1964}} However, {{harvtxt|Reid|Parker|1970}} showed that this bound is not tight for some larger values of&nbsp;<math>n</math>.{{sfnp|Reid|Parker|1970}}

{{harvtxt|Erdős|Moser|1964}} 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 [[Combinatorial proof|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.{{sfnp|Erdős|Moser|1964}}

===Paradoxical tournaments===
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>{{harvtxt|Erdős|1963}}</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 Szekeres|Esther]] and [[George Szekeres]] in 1965.{{sfnp|Szekeres|Szekeres|1965}} There is an explicit construction of <math>k</math>-paradoxical tournaments with <math>k^24^{k-1}(1+o(1))</math> players by [[Ronald Graham|Graham]] and Spencer (1971) namely the [[Paley tournament]].

===Condensation===
The [[Condensation (graph theory)|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>{{harvtxt|Harary|Moser|1966}}, Corollary 5b.</ref>