Relation between $k$ and $n$ in Alon and Spencer, 4th Edition, Section 10.3

Question

On page 184, in section 10.3 of Alon and Spencer (The Probabilistic Method, 4th Edition), line -8, it is written: "Then $$n = \sqrt{2}^{k(1+o(1))}, ..."$$ At this point in the text, what is this implication based on? Is "$k$" meant to be "$k_0$" in that expression (if so, could you explain why this asymptotic statement holds for $k_0$)? Otherwise, what is $k$? I am confused, since $k$ was not related to $n$ before this "then" statement.

Answer 1

Yes, it is meant to be $k_0$, or alternatively we can switch the two clauses and say

Then for $k \sim k_0$, $n = \sqrt{2}^{k(1+o(1))}$, so ...

If the statement $n = \sqrt{2}^{k(1+o(1))}$ holds for $k = k_0$, it automatically holds when $k \sim k_0$ (when $k = k_0(1+o(1))$), so I'll show that when $k = k_0$, $n = \sqrt{2}^{k(1+o(1))}$.

We have $f(k-1) > 1$ so $\binom{n}{k-1} 2^{-\binom{k-1}{2}} > 1$, or $\binom{n}{k-1} > 2^{\binom{k-1}{2}}$. Therefore $$ n^{k-1} \ge \binom{n}{k-1} > 2^{(k-1)(k-2)/2} \implies n > 2^{(k-2)/2} = \sqrt2^{k-2}. $$ We also have $f(k) < 1$ so $\binom nk 2^{-\binom k2} < 1$, or $\binom nk < 2^{\binom k2}$. Therefore $$ \left(\frac nk\right)^k \le \binom nk < 2^{k(k-1)/2} \implies \frac nk < 2^{(k-1)/2} = \sqrt2^{k-1}. $$ So we have sandwiched $n$: $\sqrt2^{k-2} < n < k \sqrt2^{k-1}$. In other words, $n$ is off from $\sqrt 2^k$ by a factor of between $2$ and $k \sqrt 2$, which is well within our error margin of $\sqrt 2^{o(k)}$.