A tournament on a set $V$, with $|V| = n$ is an orientation of the edges of the complete graph on $V$.
A tournament has property $S_k$ if for every set of $k$ edges, there is one who dominates them all. ($x$ dominates $y$ iff $(x,y)$ is an edge, and note that then $(y,x)$ is not).
In the book 'The Probabilistic Method' by Alon and Spencer we find this proposition:
below which we find:
Can you explain how it follows that $f(k) \le k^2s^k\ln(2)(1+o(1))$? Specifically I'm looking to understand how they came up with this bound, and not merely why it's true that if $n$ is larger than it then there is such a tournament.
With the two bounds $\binom nk < (\frac{en}{k})^k$ and $(1 - 2^{-k})^{n-k} < e^{-(n-k)/2^k}$, we can rewrite Theorem 1.2.1: its conclusion holds if $(\frac{en}{k})^ke^{-(n-k)/2^k} < 1$, or (by taking the log) $$ k \log \frac{en}{k} - \frac{n-k}{2^k} < 0. $$ Solving for $n$ is difficult, but if we do a kind of half-assed job of solving for $n$, we get $$ n > k 2^k (1 + \log n - \log k) + k. $$ To get an upper bound on $f(k)$, we want to get an upper bound on the least $n$ for which this inequality holds.
First, observe that the inequality holds (for sufficiently large $k$) if we set $n = k^3 2^k$, because then the right-hand side is only $O(k^2 2^k)$. So for sufficiently large $k$, the conclusion of Theorem 1.2.1 holds provided that $$ n > k 2^k(1 + \log (k^3 2^k) - \log k) + k $$ and this simplifies to $ (1 + o(1))k^2 2^k \log 2$.