Complete subgraphs in multipartite graphs

2009/10/08 by Pfender, Florian
#05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.0910.1447

Abstract

Turan's Theorem states that every graph of a certain edge density contains a complete graph K^k and describes the unique extremal graphs. We give a similar Theorem for l-partite graphs. For large l, we find the minimal edge density d^k_l, such that every ℓ-partite graph whose parts have pairwise edge density greater than d^k_l contains a K^k. It turns out that d^k_l=(k-2)/(k-1) for large enough l. We also describe the structure of the extremal graphs. For the case of triangles we show that d³₁₃=1/2, disproving a conjecture by Bondy, Shen, Thomasse and Thomassen.

Related

• Turan's theorem inverted
• Turán number of bipartite graphs with no K_t,t
• On the Fon-der-Flaass Interpretation of Extremal Examples for Turan's\n (3,4)-problem
• Extremal numbers of disjoint triangles in r-partite graphs
• Turán's Theorem Through Algorithmic Lens