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

Let $N=C{d}^{2d}k$ and red-blue colour $K_N$. Split its vertices into two classes of comparable size. At least half the cross-edges have one colour, say red. The bounded-degree bipartite Ramsey bound, proved by dependent random choice, gives a set $U$ in one class such that every subset of at most $d$ vertices of $U$ has at least $k$ common red neighbours in the other class.

Let $H=X\bigsqcup Y$ be a bipartition. Embed $X$ injectively into $U$. List the vertices of $Y$ and embed them one at a time. Each vertex of $Y$ has at most $d$ already embedded neighbours, whose common red neighbourhood has at least $k$ vertices; fewer than $k$ host vertices have yet been used, so a fresh choice is available. This greedily constructs a red copy of $H$. Thus

Solved by gpt-5.6-sol high.