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...
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Dokumenttyp: | Article (Journal) Kapitel/Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
1 Sep 2023
|
| Ausgabe: | Version v2 |
| In: |
Arxiv
Year: 2023, Pages: 1-16 |
| DOI: | 10.48550/arXiv.2202.14032 |
| Online-Zugang: | Verlag, kostenfrei, Volltext: https://doi.org/10.48550/arXiv.2202.14032 Verlag, kostenfrei, Volltext: http://arxiv.org/abs/2202.14032 
|
| Verfasserangaben: | Quentin Dubroff, António Girão, Eoin Hurley, and Corrine Yap |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Online veröffentlicht am 28. Februar 2022 mit dem Titel "New stepping-up constructions for multicoloured hypergraphs" Gesehen am 11.01.2024 |
| Beschreibung: | Online Resource |
| DOI: | 10.48550/arXiv.2202.14032 |