Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / B / 5

For $k\ge 1$, monotonicity of the logarithm givesThus $k!\ge (k/e{)}^k$. Bounding the numerator of the binomial coefficient by $n^k$ yields

The function $x-\log (1+x)$ has derivative $x/(1+x)$, is zero at zero, and is nonnegative for every $x>-1$. Therefore $\log (1+x)\le x$. Multiplying by $m>0$ and exponentiating givesEquality occurs at $x=0$.

Each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered vertex pairs has two independent choices of orientation. Hence the number of tournaments on the specified labelled vertex set is

Orient each edge independently and uniformly. Fix a $k$-set $A$. An outside vertex beats every member of $A$ with probability $2^{-k}$. For different outside vertices these events depend on disjoint sets of edges, so they are independent. ThusA union bound over all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ possible sets givesThe complementary event has positive probability, proving a tournament with the required domination property exists. This applies in the intended nonvacuous range $n\ge k$; the asymptotic construction below has $n>k$.

For large $k$, chooseUsing the two inequalities proved in part (a), the logarithm of the union bound is at mostNow ${\log }_e(en/k)=k{\log }_{e}2+{\log }_{e}k+O(1)$, whereas $(n-k)2^{-k}=k^2{\log }_{e}2+2k{\log }_{e}k+o(1)$. Their difference isfor all sufficiently large $k$. The existence criterion therefore applies. Since the chosen $n$ satisfieswe obtain $\boxed{f(k)\le k^2{2}^k({\log }_{e}2)(1+o(1))}$, with the usual convention that the tournament has at least $k$ vertices. If orders below $k$ were permitted, the property would be vacuous there; the same upper bound remains valid but the extremal definition would be uninteresting.