A tournament is an oriented graph $T=(V,E)$ such that $(x,x)\notin E$ for all $x\in V$, and for any two vertices $x\neq y$ exactly one of $(x,y)$ and $(y,x)$ belongs to $E$. That is, each tournament is obtained from a complete graph by orienting its edges. The name tournament is natural, since one can think of the set $V$ as a set of players in which each pair participates in a single match, where $(x,y)\in E$ iff $x$ beats $y$.
Say that a tournament has the property $P_k$ if for every set of $k$ players there is one who beats them all, i.e. , if for any subset $S\subseteq V$ of $k$ playes there exists a player $y\notin S$ such that $(y,x)\in E$ for all $x\in S$.
Threorem 3.1 (Erdos 1963) If $n\geq k^22^{k+1}$, then there is a tournament of $n$ players that has the property $P_k$.
Proof. Consider a random tournament of $n$ players, i.e., the outcome of every game is determined by the flip of fair coin. For a set $S$ of $k$ players, let $A_S$ be the event that no $y\notin S$ baets all of $S$. Each $y\notin S$ has probability $2^{-k}$ of beating all of $S$ and there are $n-k$ such possible $y$, all of whose chances are mutually independent. Hence $\text{Pr}[A_S]=(1-2^{-k})^{n-k}$ and $$\text{Pr}\left[\cup A_S\right]\leq \binom{n}{k}(1-2^{-k})^{n-k}<\frac{n^k}{k!}e^{-(n-k)/2^k}\leq n^ke^{-n/2^k}.$$ If $n\geq k^22^{k+1}$, this probability is strictly smaller than $1$. Thus, for such an $n$, with positive probability no events $A_S$ occurs. This means that there is a point in the probability space for which none of the events $A_S$ happens. This point is a tournament $T$ and this tournament has the property $P_k$.
This is an excerpt from Jukna's book "Extremal combinatorics". I am learning Chapter 3 which is Probabilistic Counting. I am not so familiar with probability theory except basic definitions but the author provides some information in the previous paragraph such as finite probability space, random variable, its mean and the notion of randomness.
I'd be very thankful if someone can explain me some unclear moments from this excerpt.
- I suppose that the probability space here is $(\Omega,P)$, where $\Omega$ is family of all possible tournaments between $n$ players and obviously $|\Omega|=2^{\binom{n}{2}}$ and for each $\omega\in \Omega$ we suppose $\text{Pr}[\omega]=2^{-\binom{n}{2}}$. Is that correct?
I did not understand why $\text{Pr}[A_S]=(1-2^{-k})^{n-k}$. Can anyone explain that in detail, please?
I understood the first inequality which follows from the fact that $\text{Pr}(\cup_{i=1}^{N}A_i)\leq\sum \limits_{i=1}^N \text{Pr}(A_i)$ but I did not understand the last two, though, I know that $\binom{n}{k}\leq \frac{n^k}{k!}$. Can anyone explain that also please?
I'll highly appreciate your help! Thanks!
EDIT: For some reason in my computation I obtained that $\text{Pr}[A_S]=2^{-k(n-k)}$. Because $A_S=\{\omega \in \Omega: \text{no}\ y\notin S \ \text{beats all of}\ S\}$. So we need to fix $n-k$ edges from each vertex belonging to $S$ which is in total $k(n-k)$. Hence we have remaining ${\binom{n}{2}}-k(n-k)$ edges and on each of them we can define 2 directions. It shows that that the answer is $\dfrac{2^{\binom{n}{2}-k(n-k)}}{2^{\binom{n}{2}}}=2^{-k(n-k)}.$
Your pobability space is correct.
We would need to fix this number of edges if the wanted every $y\notin S$ to beat all of $S$. (Because we would fix every edge between $V\setminus S$ and $S$ to the direction $V\setminus S$ to $S$. But if we want every $y\notin S$ to not beat all of $S$, we need for each $y\notin S$ at least one edge not directed to $S$, which is more permissive. The probability that $y$ does not beat all $S$ is the complementary of $y$ beat all of $S$, so it has probability $1-2^{-k}$. These probabilities are all independant for the $n-k$ vertices outside of $S$, so we get $(1-2^{-k})^{n-k}$.
Third inequality : This is straightforward to see that $e^{k/2^k}\leq e^{1/2} \leq k!, k\geq 2$. This is wrong if $k = 1$, but the theorem is trivial in this setting.