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.

Keywords

• 05C55
• 05D10
• 05C65