Generalizations of the Ruzsa-Szemeredi and rainbow Turan problems for cliques
Published version
Peer-reviewed
Repository URI
Repository DOI
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
1469-2163
Volume Title
30
Publisher
Cambridge University Press
Publisher DOI
Sponsorship
Royal Society (RP/EA/180019)
Engineering and Physical Sciences Research Council (2261055)
Engineering and Physical Sciences Research Council (2261055)