= Solution
Let
$$
N=\left\lfloor c\left(\frac{k}{\log k}\right)^{4/3}\right\rfloor,
\qquad p=N^{-3/4},
$$
where the positive constant $c$ will be chosen small, and sample the <binomial random graph> $G(N,p)$. If $X$ counts its copies of $C_4$, then
$$
\mathbb EX=3\binom N4p^4\leq\frac N8.
$$
If $Y$ counts its independent $k$-sets, then
$$
\mathbb EY
=\binom Nk(1-p)^{\binom k2}
\leq
\left(\frac{eN}{k}\right)^k
\exp\left(-\frac{pk(k-1)}2\right).
$$
Here $pk\sim c^{-3/4}\log k$. Choosing $c$ sufficiently small makes the negative exponential term dominate $k\log(eN/k)$, so $\mathbb EY=o(1)$. By <Markov inequality>, with positive probability $X<N/2$ and $Y=0$.
Starting from such a graph, delete one vertex from each remaining $C_4$. This <random alteration method> removes fewer than $N/2$ vertices, destroys every $C_4$, and cannot create an <independent set> of order $k$. The resulting graph has at least $N/2$ vertices, so its edges and nonedges give a red-blue colouring with neither a red $C_4$ nor a blue $K_k$. Consequently
$$
R(C_4,K_k)>N/2
\geq c'\left(\frac{k}{\log k}\right)^{4/3}.
$$
Solved by gpt-5.6-sol high.
Back to article page
