Repository logo
 

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

Published version
Peer-reviewed

Type

Article

Change log

Authors

Gowers, WT 
Janzer, Barnabas 

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.

Description

Keywords

math.CO, math.CO

Journal Title

Combinatorics, Probability and Computing

Conference Name

Journal ISSN

0963-5483
1469-2163

Volume Title

30

Publisher

Cambridge University Press
Sponsorship
Royal Society (RP/EA/180019)
Engineering and Physical Sciences Research Council (2261055)