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^{T h e t a (n r)}

if

s / r

is bounded away from

0

and

1

. The upper bound extends an old result of ErdH{o}s and Szemer'edi, 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.

Recommendations

Cited in

(2)

This page was built for publication: Set-coloring Ramsey numbers via codes