In Ramsey theory,we have a lower bound on the number $n=R(l,l)$ which is the smallest positive integer such that if the edges of $K_{n}$ are $2$-colored then there exists a monochromatic $K_l$.The bound is given by $R(l,l)\geq 2^{\frac{l-2}{2}}$.For $l=2$ we have $R(2,2)=2\geq 1=2^{\frac{2-2}{2}}$.So we assume $l\geq 3$.Now the proof goes as follows:
The number of ways in which the edges of $K_n$ can be $2$-colored is $2^{n\choose 2}$.Now given $l$-vertices of this graph,the number of ways the edges of $K_n$ can be $2$-colored such that $K_l$ formed by those $l$ vertices is monochromatic is given by $2.2^{{n\choose 2}-{l\choose 2}}=2^{{n\choose 2}-{l\choose 2}+1}$.Now there are $n\choose l$ ways to choose $l$ vertices out of $n$ vertices.So the number of ways in which we can $2$-colour edges of $l$-subsets of $\{1,2,...,n\}$ is ${n\choose l}.2^{{n\choose 2}-{l\choose 2}+1}$.Now the next step of the proof is where I have a doubt.The author claims that if ${n\choose l}.2^{{n\choose 2}-{l\choose 2}+1}<2^{n \choose 2}$ then there exists a $2$-coloring of $S$ for which there is no $l$-subset such that all the $2$-subsets of that are monochromatic$\color{red}{\text{(Why?)}}$.Now they show that if $n<2^{\frac{l-2}{2}}$ then the inequality is true.Hence they conclude that $R(l,l)\geq 2^{\frac{l-2}{2}}$.I am not able to understand the line that I have marked by red.Can someone help me understand this with suitable example?
Erdős is using the probabilistic method.
Suppose that we randomly $2$-color the edges of $K_n$. We ask, what is the expected number of monochromatic $K_\ell$'s? There are $\binom n\ell$ copies of $K_\ell$ in $K_n$. For each of these copies, the probability it is monochromatic is $$ \frac{2^{\binom{n}2-\binom \ell 2+1}}{2^{\binom n2}} $$ Using linearity of expectation, $$ \mathbb E[\text{# monochromatic $K_\ell$'s}]=\binom n\ell \cdot \frac{2^{\binom{n}2-\binom \ell 2+1}}{2^{\binom n2}} $$ Finally, whenever the expected number of monochromatic $K_\ell$'s is less than $1$, there must exist some particular coloring with zero monochromatic $K_\ell$'s. The above quantity is less than $1$ if and only if $ \binom n\ell\cdot 2^{\binom n2-\binom{\ell}{2}+1}< 2^{\binom{n}2}$.