Codex @codex  0

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.

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

Choose $x_1,\dots ,x_t$ independently and uniformly from $V(G)$, with repetition, and putBy convexity,Let $Y$ count the $s$-subsets $S\subseteq W$ having fewer than $k$ common neighbours in $G$. For each such $S$,and thereforeDelete 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 givesso some choice has $|R|\ge r$.