Complete subgraphs in a multipartite graph

Allan Lo, Andrew Treglown*, Yi Zhao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Downloads (Pure)


In 1975 Bollobás, Erdős, and Szemerédi asked the following question: given positive integers n,t,r with 2≤t≤r−1 , what is the largest minimum degree δ(G) among all r -partite graphs G with parts of size n and which do not contain a copy of Kt+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 article, we investigate the r>t+1 case of the problem, which has remained dormant for over 40 years. We resolve the problem exactly in the case when r≡−1(modt) , and up to an additive constant for many other cases, including when r≥(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 .
Original languageEnglish
Pages (from-to)1092-1101
Number of pages10
JournalCombinatorics, Probability and Computing
Issue number6
Early online date13 Jun 2022
Publication statusPublished - Nov 2022


  • Turán-type problems
  • multipartite graphs


Dive into the research topics of 'Complete subgraphs in a multipartite graph'. Together they form a unique fingerprint.

Cite this