A Density Tur\'an Theorem

Let $F$ be a graph which contains an edge whose deletion reduces its chromatic number. For such a graph $F,$ a classical result of Simonovits from 1966 shows that every graph on $n\ge n_0(F)$ vertices with more than $\frac{\chi (F)-2}{\chi (F)-1}\cdot \frac{n^2}{2}$ edges contains a copy of $F$. In this paper we derive a similar theorem for multipartite graphs. For a graph $H$ and an integer $\mathrm{\ell }\ge v(H)$, let $d_{\mathrm{\ell }}(H)$ be the minimum real number such that every $\mathrm{\ell }$-partite graph whose edge density between any two parts is greater than $d_{\mathrm{\ell }}(H)$ contains a copy of $H$. Our main contribution is to show that $d_{\mathrm{\ell }}(H)=\frac{\chi (H)-2}{\chi (H)-1}$ for $\mathrm{\ell }\ge {\mathrm{\ell }}_0(H)$ sufficiently large if and only if $H$ admits a vertex-colouring with $\chi (H)-1$ colours such that all colour classes but one are independent sets, and the exceptional class induces just a matching. When $H$ is a clique, this recovers a result of Pfender [Complete subgraphs in multipartite graphs, Combinatorica 32 (2012), 483–495]. We also consider several extensions of Pfender’s result.