Lesson 6

And this is true for any number of \(k\) teams! In other words, for sufficiently large \(n\), there exists a tournament with \(n\) vertices, in which for any \(k\) teams, there is a team that defeated them all.

Theorem (Erdős, 1963). For any \(k \in \mathbb{Z}_{\ge 1}\), there exists a tournament \(G(V,E)\) in which for any \(k\) vertices \(u_{1},\dotsc, u_{k} \in V\), there exists a vertex \(v \in V\) such that \((v,u_{i}) \in E\) for all \(i \in [k]\). (That is, for any \(k\) teams, there is a team that defeated them all.)

Proof. Consider a random tournament \(G(V,E)\) with \(n\) vertices: the outcome of each game (the direction of each edge) is chosen randomly with probability \(1/2\). For a set \(S \subseteq V\) of size \(k\), let \(A_{S}\) denote the event that "no \(v \not \in S\) defeated all of \(S\)". Each \(v \not \in S\) defeats all teams in \(S\) with probability \(2^{-k}\). There are \(n-k\) such \(v\), and these probabilities are independent, so \[\Pr[A_{S}]=(1-2^{-k})^{n-k}\ .\] Then \[\begin{align*}\Pr\left[\bigcup_{S} A_{S}\right]&\le&\text{(union bound)}\\&\le \sum_{S} \Pr[A_{S}] =\\&= \binom{n}{k}(1-2^{-k})^{n-k}\le&\text{(\(\binom{n}{k}\le \frac{n!}{(n-k)!}\le n^{k}\))}\\&\le n^{k}(1-2^{-k})^{n-k}\le&\text{(\(1+x \le e^{x}\), \(x=-2^{-k}\))}\\&\le n^{k}\left(e^{-2^{-k}}\right)^{n-k}= \\&=n^{k}e^{-\frac{n-k}{2^k}}=\\&=e^{\frac{k}{2^k}}\cdot \frac{n^k}{e^{\frac{n}{2^k}}}\ .\end{align*}\] Now recall that \(k\) is fixed, and we can take \(n\) arbitrarily large. Then \(e^{\frac{k}{2^k}}\) is a constant, \(n^{k}\) is a polynomial, and \(e^{n/2^k}=(e^{1/2^k})^{n}\) is an exponential (as a function of \(n\)). As is well known, any exponential eventually (for sufficiently large \(n\)) surpasses any polynomial, so the considered probability will be less than one. Thus, there exists a tournament in which the event \(A_{S}\) does not occur for any set \(S\).◼