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

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, withfinds distinct vertices $x_1,\dots ,x_t$ whose common neighbourhood in one colour has size at leastwhich 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,\dots ,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

Solved by gpt-5.6-sol high.