Count estimate for $N=2^{k/2}$

Erdős's arithmetic estimate. For $k \ge 3$ and $N = 2^{\lfloor k/2 \rfloor}$, the union bound over the $\binom{N}{k}$ candidate $k$-sets leaves positive probability mass:

stated in natural numbers as $\binom{N}{k} \cdot 2 < 2^{\binom{k}{2}}$. This is the quantitative step that makes the probabilistic method go through: the combined mass of all "bad" events is strictly smaller than the mass of the whole probability space (the $2^{\binom{N}{2}}$ graphs on $N$ vertices). Formalization note. All arithmetic is natural-number arithmetic; the factor $2^{1-\binom{k}{2}}$ is rewritten as $2 / 2^{\binom{k}{2}}$, which moves the $2$ to the left-hand side so that no negative exponent appears.