Cover Image

Tower gaps in multicolour Ramsey numbers

Resolving a problem of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower height separation between their 2-colour and q-colour Ramsey numbers. The main lemma underlying this construction is a new variant of the Erd ̋ os-Hajnal stepping-up lemma for a generaliz...

Full description

Saved in:
Bibliographic Details
Main Authors: Dubroff, Quentin (Author) , Girão, António (Author) , Hurley, Eoin (Author) , Yap, Corrine (Author)
Format: Article (Journal) Chapter/Article
Language:English
Published: 1 Sep 2023
Edition:Version v2
In: Arxiv
Year: 2023, Pages: 1-16
DOI:10.48550/arXiv.2202.14032
Online Access:Verlag, kostenfrei, Volltext: https://doi.org/10.48550/arXiv.2202.14032
Verlag, kostenfrei, Volltext: http://arxiv.org/abs/2202.14032
Get full text
Author Notes:Quentin Dubroff, António Girão, Eoin Hurley, and Corrine Yap
Description
Summary:Resolving a problem of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower height separation between their 2-colour and q-colour Ramsey numbers. The main lemma underlying this construction is a new variant of the Erd ̋ os-Hajnal stepping-up lemma for a generalized Ramsey number rk(t; q, p), which we define as the smallest integer n such that every q-colouring of the k-sets on n vertices contains a set of t vertices spanning fewer than p colours. Our results provide the first tower-type lower bounds on these numbers.
Item Description:Online veröffentlicht am 28. Februar 2022 mit dem Titel "New stepping-up constructions for multicoloured hypergraphs"
Gesehen am 11.01.2024
Physical Description:Online Resource
DOI:10.48550/arXiv.2202.14032

Similar Items