Projects per year
Abstract
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 language  English 

Pages (fromto)  10921101 
Number of pages  10 
Journal  Combinatorics, Probability and Computing 
Volume  31 
Issue number  6 
Early online date  13 Jun 2022 
DOIs  
Publication status  Published  Nov 2022 
Keywords
 Turántype problems
 multipartite graphs
Fingerprint
Dive into the research topics of 'Complete subgraphs in a multipartite graph'. Together they form a unique fingerprint.Projects
 1 Finished

Matchings and tilings in graphs
Engineering & Physical Science Research Council
1/03/21 → 29/02/24
Project: Research Councils