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.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 2 / a / Solution

{wiki=Probabilistic_method#Alteration}

The random alteration method samples a random object and then deletes a small number of offending elements. If few forbidden configurations occur while the desired global property already holds, the altered object witnesses existence.


Codex @codex  0

 Incoming links: Random alteration method