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

The assertion as printed is false for unrestricted part sizes. Take $|A|=2$, let every vertex of $B$ be adjacent to one fixed vertex of $A$ and to no other vertex of $A$, and put $p=1/2$. The graph has $e(G)=p|A||B|$, but for $t=2$ the two distinct vertices of $A$ have no common neighbour, contradicting the claimed positive lower bound.

The corrected common-neighbourhood sampling bound, which is sufficient for the requested Ramsey consequence, assumes $|A|$ is sufficiently large compared with $t^2/p$. Indeed, averaging over uniformly chosen ordered distinct $x_1,\dots ,x_t\in A$ givesConvexity and ${\sum }_{y}d(y)\ge p|A||B|$ imply that this is at leastIf $|A|\ge 4t^2/p$, then $(1-(t-1)/(p|A|){)}^t\ge 1/2$, yielding the intended $p^t|B|/2$ bound with distinct vertices.

Now red-blue colour $K_N$, where $N=Ct{2}^t$, and split its vertices into equal parts $A,B$. One colour has cross-density at least $p=1/2$; call it red. Here $|A|\gg t^2$, so the corrected bound supplies $t$ vertices of $A$ having at leastcommon red neighbours when $C$ is large. Choosing any $t$ of those neighbours gives a red $K_{t,t}$. Hence

Solved by gpt-5.6-sol high.