Ramsey numbers lower bound

Question

I have been given the following information,

${\displaystyle {\binom {n}{k}}2^{1-{\binom {k}{2}}}} < 1 \ then \ R(k,k) > n$.

Now I wish to show that for $K \geq 3$

$ R(k,k) \geq \mathrm{2}^{0.5k} $

Not sure where to start.

Answer 1

This is a relatively easy result using probabilistic method.

Take a $2$-coloring of the edges of the complete graph $K_n$, where each edge is independently colored with color 1 with probability $1/2$.

For any $k$-clique $S$, the probability of $S$ being monochrimatic is $\left(\frac{1}{2}\right)^{\binom{k}{2}-1}$ : $1/2$ for each edge and you have 2 colors available.

Then, if $X$ is the random variable representing the number of monochromatic $k$-clique in $K_n$, by linearity of expectations : $$ \mathbb{E}(X)=\binom{n}{k} \left(\frac{1}{2}\right)^{\binom{k}{2}-1}$$

You need to verify that for $n=2^{\lfloor k/2\rfloor}$, $\mathbb{E}(X)<1$. Therefore, applying Markov inequality $$ \mathbb{P}(X=0)>0$$ And there is a coloring of $K_n$ with $n=2^{\lfloor k/2\rfloor}$, with no monochromatic $k$-clique. Hence $R(k,k) > 2^{\lfloor k/2\rfloor}$