Turán number of complete multipartite graphs in multipartite graphs

Abstract

In this paper we study a multi-partite version of the Erdős--Stone theorem. Given integers $r<k$ and $t\ge 1$, let ${\text{ex}}_k(n,K_{r+1}(t))$ be the maximum number of edges of $K_{r+1}(t)$-free $k$-partite graphs with $n$ vertices in each part, where $K_{r+1}(t)$ is the complete $(r+1)$-partite graph with $t$ vertices in each part. We determine the exact value of ${\text{ex}}_k(n,K_{r+1}(t))$ for $t\le 3$, $r<k\le 2r$ and sufficiently large $n$. We also characterize all extremal graphs for $r,k$ such that $r$ divides $k$, analogous to a result of Erd\H os and Simonovits on forbidding $K_{r+1}(t)$ in general graphs.

21 pages, 1 figure. V2 focused on the case k\le 2r and t=2,3, new exact results obtained (both upper&lower bounds improved); suboptimal results for k>2r removed