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

preprint2020arXivOpen access

Abstract

Considering a natural generalization of the Ruzsa-Szemerédi problem, we prove that for any fixed positive integers r,sr,s with r<sr<s, there are graphs on nn vertices containing nre−O(log⁡n)=nr−o(1)n^{r}e^{-O(\sqrt{\log{n}})}=n^{r-o(1)} copies of KsK_s such that any KrK_r is contained in at most one KsK_s. We also give bounds for the generalized rainbow Turán problem ex⁡(n,H,\operatorname{ex}(n, H,rainbow-F)F) when FF 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 nn vertices with nr−1−o(1)n^{r-1-o(1)} copies of KrK_r such that no KrK_r is rainbow.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.