Graph with any rational density and no rich subsets of linear size

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 (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.