Ramsey and Random Graph

Question

By considering the random graph G(n,p), show that

$$R(4,k)>\left ( \dfrac{k}{3\log k} \right )^{3/2} $$

Improve this bound as much as you can.

Answer 1

This problem can be done via probabilistic method. As a hint, show that

$$\binom{n}{k}p^{\binom{k}{2}}+\binom{n}{t}(1-p)^{\binom{t}{2}}<1$$

Which will imply $R(k,t)>n$. After you do this, you'll be able to show your bound with a little extra work.