  A well-known application of the dependent random choice asserts that any
$n$-vertex graph $G$ with positive edge density contains a `rich' vertex subset
$U$ of size $n^{1-o(1)}$ such that every pair of vertices in $U$ has at least
$n^{1-o(1)}$ common neighbors. In 2003, using a beautiful construction on
hypercube, Kostochka and Sudakov showed that this is tight: one cannot remove
the $o(1)$ terms even if the edge density of $G$ is $1/2$. In this paper, we
generalize their result from pairs to tuples. To be precise, we show that given
every pair of positive integers $p<q$, there is an $n$-vertex graph $G$ for all
sufficiently large $n$ with edge density $p/q$ such that any vertex subset $U$
of size $\Omega(n)$ contains $q$ vertices, any $p+1$ of which have $o(n)$
common neighbors. The edge density $p/q$ is best possible. Our construction
uses isoperimetry and concentration of measure on high dimensional complex
spheres.
