0
$\begingroup$

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.

  1. 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?
  1. I did not understand why $\text{Pr}[A_S]=(1-2^{-k})^{n-k}$. Can anyone explain that in detail, please?

  2. 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)}.$

$\endgroup$

1 Answer 1

2
$\begingroup$
  1. Your pobability space is correct.

  2. So we need to fix $n−k$ edges from each vertex belonging to S which is in total $k(n−k)$.

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}$.

  1. Second inequality : $1+x\leq e^x$ so $(1+x)^r\leq e^{rx}, r>0$
    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.
$\endgroup$
17
  • $\begingroup$ Thanks a lot for your answer! I am reading it carefully. But was I right with the finite probability space $(\Omega, \text{Pr})$? $\endgroup$
    – RFZ
    Commented Apr 6, 2022 at 14:19
  • $\begingroup$ So I defined the finite probability space $(\Omega,\text{Pr})$ as follows: $\Omega$ - the family of all tournaments on $n$ players. Hence $|\Omega|=2^{\binom{n}{2}}$ and $\text{Pr}[\omega]=2^{-\binom{n}{2}}$ for each $\omega\in \Omega$. Suppose that $V=\{p_1,\dots,p_n\}$ be the set of players. WLOG assume that $S=\{p_1,\dots,p_k\}$. Define $A_S:=\{\omega\in \Omega: \text{no}\ y\notin S \ \text{beats all of}\ S\}$. $\endgroup$
    – RFZ
    Commented Apr 6, 2022 at 21:40
  • $\begingroup$ One can see that $A_S=\bigcap\limits_{j=1}^{n-k}A_S^{(j)}$ where $A_S^{(j)}:=\{\omega\in \Omega: \ p_{j+k}\notin S \ \text{does not beat all of}\ S\}$ for $1\leq j\leq n-k$. I know that $\text{Pr}[A_S^{(j)}]=1-2^{-k}$. But how it follows that $\text{Pr}[A_S]=(1-2^{-k})^{n-k}$? I am not so familiar with probability theory except basic definitions. Can you explaim that moment please? $\endgroup$
    – RFZ
    Commented Apr 6, 2022 at 21:40
  • $\begingroup$ @PlayGame Your probability space is right. If $A$ and $B$ are two independent events, then $\Pr(A\bigcap B) = Pr(A)Pr(B)$. Two events are independent if the issue of one event have no correlation on the other. Here, the sets of edges from $y\notin S$ to $S$ are disjoint for all $y$, so the corresponding probabilities will be independent. $\endgroup$
    – caduk
    Commented Apr 7, 2022 at 8:05
  • $\begingroup$ I was wondering can you give a more detailed explananation for that, please? I really have issues to understand that. I have never seen this before and I'd be grateful if I can see this for the first time in details $\endgroup$
    – RFZ
    Commented Apr 7, 2022 at 12:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .