Editing Tournament (graph theory) (section)

===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}}