= Solution
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.
Back to article page
