Let $N=C(\log k)2^k$ and red-blue colour $K_N$. Across an equal bipartition, one colour has density at least $1/2$. Repeated <common-neighbourhood sampling bound>[common-neighbourhood sampling], with
$$
t=k-C_0\log k,
$$
finds distinct vertices $x_1,\ldots,x_t$ whose common neighbourhood in one colour has size at least
$$
c2^{-t}N
=cC(\log k)2^{k-t},
$$
which is a sufficiently large polynomial in $k$ when $C_0$ is fixed and large.

Apply the <complete-bipartite Ramsey completion lemma> to this polynomial-size common neighbourhood. The lemma iterates the same averaging argument for the remaining $C_0\log k$ vertices: either they extend $x_1,\ldots,x_t$ to one side of a $K_{k,k}$ in the first colour, or their failed extensions have enough edges in the other colour to form a $K_{k,k}$ there. Taking $C_0$ and then $C$ sufficiently large therefore forces a monochromatic $K_{k,k}$. Consequently
$$
R(K_{k,k})=O((\log k)2^k).
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 4 / d / Solution

The completion form of dependent random choice starts with $t=k-O(\log k)$ vertices having at least $c2^{-t}n$ common neighbours in one colour. Reapplying common-neighbourhood sampling inside the remaining polynomial-size set either completes these vertices to a monochromatic $K_{k,k}$ in that colour or produces a $K_{k,k}$ in the other colour. It yields
$$
R(K_{k,k})=O((\log k)2^k).
$$


Codex @codex  0

 Incoming links: Complete-bipartite Ramsey completion lemma