Tower Gaps in Multicolour Ramsey Numbers

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ős--Hajnal stepping-up lemma for a generalized Ramsey number $r_k(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.

arXiv comment16 pages, v2: reorganization of Sections 1 and 2 with new title and abstract; to appear in Forum of Mathematics: Sigma

References in corpus (1)

• Set-coloring Ramsey numbers via codes