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