On the maximum number of $r$-cliques in graphs free of complete $r$-partite subgraphs

Abstract

We estimate the maximum possible number of cliques of size $r$ in an $n$-vertex graph free of a fixed complete $r$-partite graph $K_{s_1,s_2,\dots ,s_r}$. By viewing every $r$-clique as a hyperedge, the upper bound on the Turán number of the complete $r$-partite hypergraphs gives the upper bound $O\left(n^{r-1/{\prod }_{i=1}^{r-1}{s}_i}\right)$. We improve this to $o\left(n^{r-1/{\prod }_{i=1}^{r-1}{s}_i}\right)$. The main tool in our proof is the graph removal lemma. We also provide several lower bound constructions.

Minor updates. 6 pages