= Solution
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).
$$
Solved by gpt-5.6-sol high.
Back to article page
