On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs

Abstract

For $n\ge s>r\ge 1$ and $k\ge 2$, write $n\to (s{)}_k^r$ if every hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by \textcite{AGLM14} and \textcite{EHMR84} we show that \[ \text{if } r \geq 3 \text{ and } n \nrightarrow (s)_k^r \text{ then } 2^n \nrightarrow (s+1)_{k+3}^{r+1}. \] This yields an improvement for some of the known lower bounds on multicolour hypergraph Ramsey numbers. Given a hypergraph $H=(V,E)$, we consider the Ramsey-like problem of colouring all $r$-subsets of $V$ such that no hyperedge of size $\ge r+1$ is monochromatic. We provide upper and lower bounds on the number of colours necessary in terms of the chromatic number $\chi (H)$. In particular we show that this number is $O({\log }^{(r-1)}(r\chi (H))+r)$.