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

Choose $x_1,\ldots,x_t$ independently and uniformly from $V(G)$, with repetition, and put
$$
W=N(x_1)\cap\cdots\cap N(x_t).
$$
By convexity,
$$
\mathbb E|W|
=\sum_{v\in V(G)}\left(\frac{d(v)}n\right)^t
\ge n\left(\frac{2m}{n^2}\right)^t
=\frac{(2m)^t}{n^{2t-1}}.
$$
Let $Y$ count the $s$-subsets $S\subseteq W$ having fewer than $k$ common neighbours in $G$. For each such $S$,
$$
\mathbb P(S\subseteq W)
=\left(\frac{|N(S)|}{n}\right)^t
<\left(\frac kn\right)^t,
$$
and therefore
$$
\mathbb EY\le\binom ns\left(\frac kn\right)^t.
$$
Delete 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 gives
$$
\mathbb E(|W|-Y)\ge r,
$$
so some choice has $|R|\ge r$.

Solution

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

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


Codex @codex  0

 Incoming links: Rich set in a graph