Set-coloring Ramsey numbers via codes

Abstract

For positive integers $n,r,s$ with $r>s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is guaranteed to be a monochromatic clique on $n$ vertices, that is, a subset of $n$ vertices where all of the edges between them receive a common color. In particular, the case $s=1$ corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on $R(n;r,s)$ which imply that $R(n;r,s)=2^{\hat{I}˜(nr)}$ if $s/r$ is bounded away from $0$ and $1$. The upper bound extends an old result of Erdős and Szemerédi, who treated the case $s=r-1$, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs.

11 pages