Graphs with Many Copies of a Given Subgraph

Abstract

Let $c>0$, and $H$ be a fixed graph of order $r$. Every graph on $n$ vertices containing at least $cn^{r}$ copies of $H$ contains a "blow-up" of $H$ with $r-1$ vertex classes of size $\big\lfloor c^{r^{2}}\ln n\big\rfloor $ and one vertex class of size greater than $n^{1-c^{r-1}}$. A similar result holds for induced copies of $H$.