Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 3 / c / Solution

Let $N=\lceil k^{1+ϵ}\rceil$ and red-blue colour $K_N$. One colour class gives a graph $G$ withApply part (a) with $s=d$, the common-neighbour target equal to $k$, and an integerThe first term in its hypothesis is at least $c_1^{t}N$. The error term satisfiesSince $N/k=k^{ϵ}\to \infty$, the difference is at least $k$ for all sufficiently large $k$, depending only on $d$ and $ϵ$. Part (a) therefore gives a $(d,k)$-rich set of size at least $k$, and part (b) embeds $H$ in this colour. Hencefor sufficiently large $k$.