Editing Tournament (graph theory) (section)

===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]].