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

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.