Lesson 3

The results of such a tournament are conveniently represented by a graph: we draw \(n\) points (vertices) corresponding to teams, and for any two teams \(i\) and \(j\), we draw an arrow from \(i\) to \(j\) if \(i\) defeated \(j\). In this graph, we are interested in paths that traverse all vertices following the arrows. These are called Hamiltonian paths.

Below is a tournament with 189 Hamiltonian paths. For example, \(0 \to 1 \to 4 \to 2 \to 5 \to 3 \to 6\) and \(6 \to 4 \to 5 \to 3 \to 2 \to 0 \to 1\).

The following theorem shows that there exist tournaments with a very large number of Hamiltonian paths: more than \(c^{n}\) for any constant \(c\). Apparently, this theorem is the first example of an application of the probabilistic method. The proof, in particular, will use the following simple yet important observation: to show that a random variable can take a sufficiently large value, it is enough to show that its expected value is sufficiently large. More formally, if for a random variable \(\alpha \colon U \to \mathbb{R}\) we have \(\operatorname{E}[\alpha] \ge t\), then there exists \(u \in U\) such that \(\alpha(u) \ge t\).

Theorem (Szele, 1943). There exists a tournament on \(n\) vertices with at least \[\frac{n!}{2^{n-1}}\] Hamiltonian paths.

Proof. Consider a random tournament: between each pair of vertices, draw an edge in a random direction (independently each time). Now, compute the expected number of Hamiltonian paths in the resulting graph. As usual, we use the linearity of expectation and compute it as the sum of expectations of indicators. Consider a permutation \(\pi\) of the vertices. What is the probability that the graph contains a Hamiltonian path on this permutation? The probability is \(\frac{1}{2^{n-1}}\): each edge between adjacent vertices must be oriented in the required direction. Thus, the expected number of Hamiltonian paths is \[n! \cdot \frac{1}{2^{n-1}} .\] This, in turn, means that there must exist a tournament with at least this many Hamiltonian paths.◼