Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques

Abstract

Abstract Considering 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 $n^{r}e^{-O\left(\sqrt{\log{n}}\right)}=n^{r-o(1)}$ copies of K s such that any K r is contained in at most one K s . 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 $n^{r-1-o(1)}$ copies of K r such that no K r is rainbow.

Topics & Concepts