 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/b/5/b/iii/solution

For large

k

, choose

n = ⌈ 2^{k} {k^{2} lo g_{e} 2 + 2 k lo g_{e} k} ⌉ .

Using the two inequalities proved in part (a), the logarithm of the union bound is at most

k lo g_{e} (e n / k) - (n - k) 2^{- k} .

Now

lo g_{e} (e n / k) = k lo g_{e} 2 + lo g_{e} k + O (1)

, whereas

(n - k) 2^{- k} = k^{2} lo g_{e} 2 + 2 k lo g_{e} k + o (1)

. Their difference is

- k lo g_{e} k + O (k) < 0

for all sufficiently large

k

. The existence criterion therefore applies. Since the chosen

n

satisfies

n = k^{2} 2^{k} (lo g_{e} 2) (1 + O (\frac{l o g k}{k})),

we obtain

f (k) \leq k^{2} 2^{k} (lo g_{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.

 New to topics? Read the docs here!