A Density Turán Theorem

Abstract

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{\ddot{I}‡(F)-2}{\ddot{I}‡(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 $\ell \ge v(H)$, let $d_{\ell }(H)$ be the minimum real number such that every $\ell$-partite graph whose edge density between any two parts is greater than $d_{\ell }(H)$ contains a copy of $H$. Our main contribution is to show that $d_{\ell }(H)=\frac{\ddot{I}‡(H)-2}{\ddot{I}‡(H)-1}$ for $\ell \ge {\ell }_0(H)$ sufficiently large if and only if $H$ admits a vertex-colouring with $\ddot{I}‡(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.

28 pages, 2 figures