Tournament, Ramsey Number A tournament $T_{n}$ on a set V of n players is an orientation of the edged of a complete graph $K_{n}$. The name of the 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) is in the tournament $T_{n}$ and iff x beats y. we say that $T_{n}$ has the property $S_{k}$ if for every given set of k players, there is one other player who beats them all.
Question: for all k $\geq$ 1, does there exist n and $T_{n}$ such that $T_{n}$ has the property $S_{k}$?
Proposition: If $\binom{n}{k}(1-\frac{1}{2^{k}})<1$, then the answer is yes.
Comment and proof

*

*For fixed k, prove that $\lim_{n \rightarrow + \infty} \binom{n}{k}(1-\frac{1}{2^{k}})^{n-k}=0$.


*We are going to see that whenever $n>>k$, a tournament chosen at random is very likely to have the property $S_{k}$.
(a) Let f(k) the smallest number of players such that there exist a tournament $T_{f(K)}$ possessing the property $S_{k}$. Using the result of the proposition explain why if $\frac{ne}{k}e^{-(n-k)/(k2^{k})}<1$, then $f(k)\leq n$
(b) Choose $n(k)=(In2+2\frac{In K}{k})k^{2}2^{k}$, deduce that for large k, $f(k)\leq In(2)k^{2}2^{k}(1+o(1))$.
Szekeres ('68) has proved that $f(k)\geq Ck2^{k}$; for example you may check by your means that f(1)=3 and f(2)=7.


*We turn to the proof of the proposition, the integer n is now fixed. We choose uniformly randomly an orientation of $k_{n}$. For K $\in p_{k}([n])$, let $A_{k}$ denote the event 'no other player beats all the k players of K'.

(a) Explain why for any K $\in p_{k}([n]),$ P$(A_{k})=(1-\frac{1}{2^{k}})^{n-k}$.
(b) Prove that P$(\bigcup_{K\in p_{k}([n])} A_{K})\leq\binom{k}{n}(1-\frac{1}{2^{k}})^{n-k}$.
(c) End the proof of the proposition.
 A: What an interesting problem!
For the first question, it is probably prudent to write out the definition of the binomial coefficient. Then we see that if one cancels the $k!$ term with the numerator, one obtains $(n-k)$ many terms which become arbitrarily close to $1$ for suff. large $n$. Since the other terms remain fixed, and one has a fixed number less than $1$ to the power of $n-k$ as the other factor, we conclude 1.
The second question may be treated as thus:
(a) Here we use a well-known bound, namely
$$
\binom{n}{k} \le \left( \frac{n e}{k} \right)^k.
$$
Then the inequality of the proposition is implied by
$$
\left( \frac{n e}{k} \right)^k \left( 1 - \frac{1}{2^k} \right)^{n-k} < 1,
$$
and very probably this is equivalent to whatever the desired expression is (something must have gone wrong with your formatting there).
(b) Inserting the formula for $n(k)$ into this inequality very probably gives an expression that is asymptotically $\le 1$. Using the $o(1)$, we make it $<1$.
The third question is resolved as follows:
(a) There are $n-k$ other players. Since the probability was choosen uniformly, the events that any of those players does not beat all of $K$ are independent of each other. So whatever the probability for a single player, their intersection (no player beats all of $K$) will be the probability for one player to the $(n-k)$-th. Now the probability of a single player to defeat all of $K$ is $1/2^k$, so the probability of the complement is $1 - 1/2^k$, QED.
(b) is obvious since there are $\binom{n}{k}$ ways of choosing $k$ players out of $n$.
(c) follows immediately because if the probability is less then one, the probability of the complement is larger than zero. So there is at least one orientation for which
$$
\bigcup_{K \in p_k([n])} A_K
$$
fails.
