Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 122 / 2

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

Choose $t$ vertices $x_1,\dots ,x_t$ independently and uniformly from $V(G)$, allowing repetitions, and letBy Jensen inequality applied to the convex function $z\mapsto z^t$,

Let $Y$ count the $s$-subsets $S\subseteq X$ having fewer than $k$ common neighbours in $G$. For each such $S$, the probability that $S\subseteq X$ issoThe assumed inequality gives $\mathbb{E}(|X|-Y)\ge r$, so some choice has $|X|-Y\ge r$. Delete one vertex from each bad $s$-subset of $X$. The remaining set $R$ has size at least $|X|-Y\ge r$ and contains no bad $s$-subset, so it is $(s,k)$-rich. This is the basic dependent random choice argument.

Embed the part $A$ injectively into the rich set in a graph $R$. List the vertices of $B$ as $b_1,\dots ,b_q$. When embedding $b_i$, the images of its at most $s$ neighbours in $A$ have at least $|H|$ common neighbours in $G$: extend that image set to an $s$-subset of $R$ if necessary, noting that enlarging a set can only shrink its common neighbourhood. At most $|H|-1$ vertices have already been used, so one common neighbour remains available for $b_i$. Choosing it embeds every edge incident with $b_i$ and keeps the map injective. Continuing greedily embeds $H$ in $G$. This is the rich-set embedding lemma.

Let $N=2^{4d}$ and colour the edges of $K_N$ red and blue. One colour, say red, forms a graph $G$ withApply part (a) withIts positive term satisfieswhileThe difference is at least $2^{d-1}$, so $G$ contains a $(d,2^d)$-rich set of size at least $2^{d-1}$.

The hypercube graph $Q_d$ is bipartite according to the parity of the sum of its coordinates. Each part has $2^{d-1}$ vertices, every vertex has degree $d$, and $|Q_d|=2^d$. Part (b) therefore embeds a red copy of $Q_d$. Every red-blue colouring of $K_{2^{4d}}$ has a monochromatic copy, proving