Detalles de una prueba de que un torneo tiene propiedad $S_k$

Question

(Edit: Mientras que el contexto no es el tema central de mi pregunta, me he decidido a incluir de todos modos para hacer la pregunta un poco más de búsqueda.)

Algunos detalles técnicos se omiten de un teorema en Alon y Spencer El Método de probabilidades.

Un torneo en $n$ jugadores que se dice que tiene la propiedad $S_k$ si, para cualquier selección de $k$ a los jugadores, hay otro jugador que gana a todos ellos. El teorema establece que un torneo tiene esta propiedad proporciona $$ \binom{n}{k}(1 - 2^{-k})^{n-k} < 1. $$

Deje $f(k)$ denotar el más pequeño $n$ la satisfacción de la desigualdad anterior (como una función de la $k$). Con el fin de encontrar un límite superior en $f(k)$, el autor hace las siguientes sustituciones:

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

Creo que la implicación es ahora para escribir $n$ como una función de la $k$ que $n$ satisface $$ \left(\frac{en}{k}\right)^k e^{-(n-k)/2^k} < 1. $$

¿Cómo puedo aislar $n$ en esta expresión? Se omiten los detalles, pero el autor de los estados $$ n \geq k^2 2^k (\ln 2) (1 + o(1)), $$ así $$ f(k) \leq k^2 2^k (\ln 2) (1 + o(1)). $$

Answer 1

Parece que el $\leq$ al final debería ser $\geq$.

Ya que la función en el lado izquierdo es unimodal y es cero cuando $n=0$$n=\infty$, la desigualdad

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

se cumple en dos intervalos de la forma $n \in [0,a) \cup (b,\infty)$. Consideremos $=$ en lugar de $<$ por la simplicidad. Reorganizar un poco los rendimientos

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

y en la toma de $k^\text{th}$ raíces obtenemos

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

Ahora vamos a $n = k2^k m$, por lo que, al multiplicar por $-k^{-1} 2^{-k}$,

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

Por tanto, tenemos

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

donde $W$ es la función W de Lambert. Si se elige la rama de $W = W_0$ a continuación, se obtiene el intervalo de endpoint $a$ definido anteriormente, y si elegimos $W = W_{-1}$ obtenemos el extremo de $b$.

Específicamente, desde $n = k 2^k m$ hemos

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

Ahora$W_0(x) = x + O(x^2)$$x \to 0$, por lo que

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

como $k \to \infty$. Del mismo modo, $W_{-1}(x) = \log(-x) + O\Bigl(\log(-\log(-x))\Bigr)$$x \to 0^-$, por lo que

$$ \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} $$

como $k \to \infty$.

En otras palabras, si

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

luego

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

o

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

como $k \to \infty$.