Lesson 5

Another common way to non-constructively prove the existence of something is to take a random object and prove that it has the desired properties with non-zero probability. This is called the probabilistic method.

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 has beaten all of them.)

Proof. Consider a random tournament \(G(V,E)\) on \(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 “no \(v \not \in S\) has beaten all of \(S\)”. Each \(v \not \in S\) beats all teams from \(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 \sum_{S} \Pr[A_{S}]&\text{(union bound)}\\&= \binom{n}{k}(1-2^{-k})^{n-k}\\&\le n^{k}(1-2^{-k})^{n-k}&\text{(\(\binom{n}{k}\le n^{k}\))}\\&\le n^{k}\left(e^{-2^{-k}}\right)^{n-k}&\text{(\(1+x \le e^{x}\), \(x=-2^{-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*}\] Recall now 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 function (as functions of \(n\)). An exponential function grows faster than a polynomial function, hence, for large enough \(n\), the considered probability is less than one. Therefore, there exists a tournament in which the event \(A_{S}\) does not occur for any set \(S\).◼