Tower gaps in multicolour Ramsey numbers

• Verfasst von: Dubroff, Quentin [VerfasserIn]
• Verfasst von: Girão, António [VerfasserIn]
• Verfasst von: Hurley, Eoin [VerfasserIn]
• Verfasst von: Yap, Corrine [VerfasserIn]
• Titel: Tower gaps in multicolour Ramsey numbers
• Verf.angabe: Quentin Dubroff, António Girão, Eoin Hurley, and Corrine Yap
• Ausgabe: Version v2
• E-Jahr: 2023
• Jahr: 1 Sep 2023
• Umfang: 16 S.
• Fussnoten: Online veröffentlicht am 28. Februar 2022 mit dem Titel "New stepping-up constructions for multicoloured hypergraphs" ; Gesehen am 11.01.2024
• Titel Quelle: Enthalten in: De.arxiv.org
• Ort Quelle: [Erscheinungsort nicht ermittelbar] : Arxiv.org, 1991
• Jahr Quelle: 2023
• Band/Heft Quelle: (2023), Artikel-ID 2202.14032, Seite 1-16
• DOI: doi:10.48550/arXiv.2202.14032
• Datenträger: Online-Ressource
• Sprache: eng
• Sach-SW: Mathematics - Combinatorics
• K10plus-PPN: 1818872021

Abstract

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.