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

A set $R\subseteq V(G)$ is $(s,k)$-rich if every $s$-element subset of $R$ has at least $k$ common neighbours.

Choose $x_1,\dots ,x_t$ independently and uniformly from $V(G)$, with repetition, and putBy convexity,Let $Y$ count the $s$-subsets $S\subseteq W$ having fewer than $k$ common neighbours in $G$. For each such $S$,and thereforeDelete one vertex from every bad $s$-subset of $W$. The remaining set $R$ is $(s,k)$-rich and satisfies $|R|\ge |W|-Y$. The hypothesis givesso some choice has $|R|\ge r$.

Choose a bipartition $V(H)=A\bigsqcup B$ and inject $A$ into the $(d,k)$-rich set $R$. For each $b\in B$, the images of its neighbours form a set of at most $d$ vertices of $R$. Extend it, if necessary, to a $d$-element subset of $R$. Richness supplies at least $k$ common neighbours in $G$.

Embed the vertices of $B$ one at a time. At every step fewer than $k$ vertices have already been used, while at least $k$ common neighbours are available, so one unused choice remains. This greedy embedding preserves every edge of $H$ and proves

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$.