Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold

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 a subset of

n

vertices where all of the edges between them receive a common color. If

n

is fixed and

f r a c s r

is less than and bounded away from

1 - f r a c 1 n - 1

, then

R (n; r, s)

is known to grow exponentially in

r

, while if

f r a c s r

is greater than and bounded away from

1 - f r a c 1 n - 1

, then

R (n; r, s)

is bounded. Here we prove bounds for

R (n; r, s)

in the intermediate range where

f r a c s r

is close to

1 - f r a c 1 n - 1

by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.

This page was built for publication: Set-coloring Ramsey numbers and error-correcting codes near the zero-rate threshold