Lower bound for the Ramsey number $R(3,t)$

Solution 1:

Let $Y$ be the number of triangles in $G$, let $Z$ be the number of copies of $K_t$ with no edge in $G$, and let $X = Y + Z$. As you have observed, by linearity of expectation, $$ E(X) = E(Y) + E(Z) = {{n}\choose{3}}p^3 + {{n}\choose{t}}(1-p)^t. $$

The key is that, with positive probability, $X \leq E(X)$. Hence, there exists $G \in \mathcal G(n,p)$ such that $X \leq {{n}\choose{3}}p^3 + {{n}\choose{t}}(1-p)^t$. Now you have a specific graph to which you can apply the vertex-deletion process that you described.

At this point, it's enough to show that there exists a positive constant $c$ such that for all $t \geq 3$, there exist $n$ and $p$ such that $$ n - {{n}\choose{3}}p^3 - {{n}\choose{t}}(1-p)^t \geq c \biggl(\frac{t}{\log t}\biggr)^{\frac{3}{2}}. \tag{1}\label{eq:R3tBound} $$ Here's a hint: Let $n = 2c\bigl(\frac{t}{\log t}\bigr)^{\frac{3}{2}}$. If $p$ is a function of $n$ (and hence of $t$) such that $$ {{n}\choose{3}}p^3 + {{n}\choose{t}}(1-p)^t \leq c \biggl(\frac{t}{\log t}\biggr)^{\frac{3}{2}}, $$ then the desired inequality \eqref{eq:R3tBound} follows immediately.