Dominated sets in tournament

Question

A dominated set is a set of vertices $S$ in a tournament $T$ such that there is a vertex $v\in T\setminus S$ that points at all the vertices in S

1. Show that every tournament on $2^k$ vertices contains a set of at most $k$ vertices that is not dominated

2. Show that if $\binom{n}{k}(1-\frac{1}{2^k})^{n-k} \lt 1$
   then there is an $n$-vertex tournament so that every set of $k$ vertices is dominated

3. Use 2 to get an explicit estimate for the size of the smallest tournament in which every $k$-set is dominated

I have solved part 1 of the question, but don't know how to approach 2 and 3

Answer 1

For part 2, use the probabilistic method. For each pair of vertices $\{x,y\}$, orient the edge from $x$ to $y$ with probability 1/2 and from $y$ to $x$ with probability 1/2. For each set of size $k$, calculate the probability that it is not dominated and then use the union bound.

For part 3, we use the following two inequalities: $\dbinom{n}{k} \leq {\left( \dfrac{en}{k}\right)}^k$ and $1-x \leq e^{-x}$.

Thus, sufficient is that: $\left(\dfrac{en}{k}\right)^k e^{-\frac{(n-k)}{2^k}}<1$.

To achieve this, we set $n=k^22^k+k$.

The L.H.S. is then at most $\left(e(k2^k+1)\right)^ke^{-k^2}$, which is less than 1 for sufficiently large $k$ because the first term is dominated by $2^{k^2}$ essentially which is smaller than $e^{k^2}$.