Generalizations of the Ruzsa-Szemeredi and rainbow Turan problems for cliques

Abstract

onsidering a natural generalization of the Ruzsa–Szemerédi problem, we prove that for any fixed positive integers r, s with r < s, there are graphs on n vertices containing copies of Ks such that any Kr is contained in at most one Ks. We also give bounds for the generalized rainbow Turán problem ex (n, H, rainbow - F) when F is complete. In particular, we answer a question of Gerbner, Mészáros, Methuku and Palmer, showing that there are properly edge-coloured graphs on n vertices with copies of Kr such that no Kr is rainbow.