I am reading an example in a text about the Probabilistic Method, and how to use it to know if there is a coloring of a graph without having monochromatic cliques of size k (k vertices). The following theorem is used in this example:
If $\binom n2 2^{-\binom k2 +1} < 1$, then it is possible to color the edges of $K_n$ with two colors so that it has no monochromatic $K_k$ subgraph.
($K_n$ is the graph with n vertices and $\binom n 2$ edges, similarly for k)
The book applies this to an example to find a coloring of $K_{1000}$ with no monochromatic clique of size $K_{20}$:
I do not understand why it is important to note that $n\leq 2^{k/2}$ or why we are using $\binom nk$ instead of $\binom n2$. If anyone could answer this and explain what you think I am missing here, it would be very helpful.
The statement in the yellow box appears to be a mistake and should say $\binom{n}{k}$ rather than $\binom{n}{2}$. The quantity $\binom{n}{k}2^{-\binom{k}{2}+1}$ counts the expected number of monochromatic cliques of size $k$ in a graph on $n$ vertices, where each edge is equally likely to be colored with either color. For a given set of $k$ vertices, the probability they form a monochromatic clique is $2\cdot \left(\frac{1}{2}\right)^{\binom{k}{2}}=2^{-\binom{k}{2}+1}$, and there are $\binom{n}{k}$ (not $\binom{n}{2}$) such sets of $k$ vertices.
For your second question, they are trying to prove that $\binom{n}{k}2^{-\binom{k}{2}+1}<1$. Thus you need some way to compare the binomial coefficient to the exponential term. The exponential term is roughly $2^{-k^2/2}$, while the binomial term is roughly $n^k/k!$. Hence the numerators cancel if we have $n \approx 2^{k/2}$, as this implies $n^k \approx 2^{k^2/2}$. This is the reason for bounding $n$ by $2^{k/2}$.