The Erdős-Hajnal hypergraph Ramsey problem

Abstract: Given integers

2 l e t l e k + 1 l e n

, let

g_{k} (t, n)

be the minimum

N

such that every red/blue coloring of the

k

-subsets of

1, l d o t s, N

yields either a

(k + 1)

-set containing

t

red

k

-subsets, or an

n

-set with all of its

k

-subsets blue. ErdH{o}s and Hajnal proved in 1972 that for fixed

2 l e t l e k

, there are positive constants

c_{1}

and

c_{2}

such that

2^{c_1 n} < g_k(t, n) < twr_{t-1} (n^{c_2}),

where

t w r_{t - 1}

is a tower of 2's of height

t - 2

. They conjectured that the tower growth rate in the upper bound is correct. Despite decades of work on closely related and special cases of this problem by many researchers, there have been no improvements of the lower bound for

2 < t < k

. Here we settle the ErdH{o}s-Hajnal conjecture in almost all cases in a strong form, by determining the correct tower growth rate, and in half of the cases we also determine the correct power of

n

within the tower. Specifically, we prove that if

2 < t < k - 1

and

k - t

is even, then

g_k(t, n) = twr_{t-1} (n^{k-t+1 + o(1)}).