Details from a Proof that a Tournament has Property $S_k$

517 Views Asked by At

(Edit: While the context is not central to my question, I decided to include it anyway to make the question a little more searchable.)

Some technical details are omitted from a theorem in Alon and Spencer's The Probabilistic Method.

A tournament on $n$ players is said to have property $S_k$ if, for any selection of $k$ players, there is another player that beats them all. The theorem states that a tournament has this property provided $$ \binom{n}{k}(1 - 2^{-k})^{n-k} < 1. $$

Let $f(k)$ denote the smallest $n$ satisfying the inequality above (as a function of $k$). In order to find an upper bound on $f(k)$, the author makes the following replacements:

$$ \binom{n}{k} \leq \left(\frac{en}{k}\right)^k $$ and $$ (1 - 2^{-k})^{n-k} \leq e^{-(n-k)/2^k}. $$

I believe the implication is now to write $n$ as a function of $k$ given that $n$ satisfies $$ \left(\frac{en}{k}\right)^k e^{-(n-k)/2^k} < 1. $$

How can I isolate $n$ in this expression? The details are omitted, but the author states $$ n \geq k^2 2^k (\ln 2) (1 + o(1)), $$ so $$ f(k) \leq k^2 2^k (\ln 2) (1 + o(1)). $$

1

There are 1 best solutions below

1
On BEST ANSWER

It seems that the $\leq$ at the end should be $\geq$.

Since the function on the left-hand side is unimodal and is zero when $n=0$ and $n=\infty$, the inequality

$$ \left(\frac{en}{k}\right)^k e^{-(n-k)/2^k} < 1 $$

is satisfied in two intervals of the form $n \in [0,a) \cup (b,\infty)$. Let's consider $=$ instead of $<$ for simplicity. Rearranging a little yields

$$ n^k e^{-n/2^k} = \left(\frac{k}{e}\right)^k e^{-k/2^k}, $$

and on taking $k^\text{th}$ roots we get

$$ n e^{-n/(k2^k)} = \frac{k}{e} e^{-1/2^k}. $$

Now let $n = k2^k m$, so that, upon multiplying through by $-k^{-1} 2^{-k}$,

$$ -m e^{-m} = -2^{-k} e^{-1-1/2^k}. $$

We therefore have

$$ m = -W\left(-2^{-k}e^{-1-1/2^k}\right), $$

where $W$ is the Lambert W function. If we choose the branch $W = W_0$ then we obtain the interval endpoint $a$ defined above, and if we choose $W = W_{-1}$ we obtain the endpoint $b$.

Specifically, since $n = k 2^k m$ we have

$$ a = -k2^k W_0\left(-2^{-k}e^{-1-1/2^k}\right). $$

Now $W_0(x) = x + O(x^2)$ as $x \to 0$, so

$$ \begin{align} a &= -k2^k \left(-2^{-k}e^{-1-1/2^k}\right) + O(k2^{-k}) \\ &= k/e + O(k2^{-k}) \end{align} $$

as $k \to \infty$. Similarly, $W_{-1}(x) = \log(-x) + O\Bigl(\log(-\log(-x))\Bigr)$ as $x \to 0^-$, so

$$ \begin{align} b &= -k2^k \left[\log\left(2^{-k}e^{-1-1/2^k}\right) + O(\log k)\right] \\ &= k^2 2^k \log2 + O(k 2^k\log k) \end{align} $$

as $k \to \infty$.

In other words, if

$$ \left(\frac{en}{k}\right)^k e^{-(n-k)/2^k} < 1 $$

then either

$$ 0 \leq n < \frac{k}{e}\left(1+O(2^{-k})\right) $$

or

$$ n > k^2 2^k \log 2 \left(1+O\left(\frac{\log k}{k}\right)\right) $$

as $k \to \infty$.