Generalizations of the Ruzsa-Szemeredi and rainbow Turan problems for cliques
View / Open Files
Authors
Gowers, WT
Janzer, Barnabas
Publication Date
2021Journal Title
Combinatorics, Probability and Computing
ISSN
0963-5483
Publisher
Cambridge University Press
Volume
30
Issue
4
Pages
591-608
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Gowers, W., & Janzer, B. (2021). Generalizations of the Ruzsa-Szemeredi and rainbow Turan problems for cliques. Combinatorics, Probability and Computing, 30 (4), 591-608. https://doi.org/10.1017/S0963548320000589
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.
Keywords
math.CO, math.CO
Sponsorship
Royal Society (RP/EA/180019)
Engineering and Physical Sciences Research Council (2261055)
Identifiers
External DOI: https://doi.org/10.1017/S0963548320000589
This record's URL: https://www.repository.cam.ac.uk/handle/1810/335136
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk