Complete subgraphs in a multipartite graph

Abstract

In 1975 Bollobás, Erd\H os, and Szemerédi asked the following question: given positive integers $n,t,r$ with $2\le t\le r-1$, what is the largest minimum degree $\delta (G)$ among all $r$-partite graphs $G$ with parts of size $n$ and which do not contain a copy of $K_{t+1}$? The $r=t+1$ case has attracted a lot of attention and was fully resolved by Haxell and Szabó, and Szabó and Tardos in 2006. In this paper we investigate the $r>t+1$ case of the problem, which has remained dormant for over forty years. We resolve the problem exactly in the case when $r\equiv -1(\mathrm{mod}t)$, and up to an additive constant for many other cases, including when $r\ge (3t-1)(t-1)$. Our approach utilizes a connection to the related problem of determining the maximum of the minimum degrees among the family of balanced $r$-partite $rn$-vertex graphs of chromatic number at most $t$.

References in corpus (1)

• Turán number of disjoint triangles in 4-partite graphs