A set $R\subseteq V(G)$ is <rich set in a graph>[$(s,k)$-rich] when every $s$-element subset of $R$ has at least $k$ common neighbours.

Choose $t$ vertices $x_1,\ldots,x_t$ independently and uniformly from $V(G)$, allowing repetitions, and let
$$
X=N(x_1)\cap\cdots\cap N(x_t).
$$
By <Jensen inequality> applied to the convex function $z\mapsto z^t$,
$$
\mathbb E|X|
=\sum_{v\in V(G)}\left(\frac{d(v)}n\right)^t
\geq n\left(\frac{2m}{n^2}\right)^t
=\frac{(2m)^t}{n^{2t-1}}.
$$

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$ is
$$
\left(\frac{|N(S)|}{n}\right)^t<\left(\frac kn\right)^t,
$$
so
$$
\mathbb EY\leq\binom ns\left(\frac kn\right)^t.
$$
The assumed inequality gives $\mathbb E(|X|-Y)\geq r$, so some choice has $|X|-Y\geq r$. Delete one vertex from each bad $s$-subset of $X$. The remaining set $R$ has size at least $|X|-Y\geq r$ and contains no bad $s$-subset, so it is $(s,k)$-rich. This is the basic <dependent random choice> argument.

Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-122/2/a/solution