A note on the Erdős-Hajnal hypergraph Ramsey problem

Abstract

We show that there is an absolute constant $c>0$ such that the following holds. For every $n>1$, there is a 5-uniform hypergraph on at least $2^{2^{c{n}^{1/4}}}$ vertices with independence number at most $n$, where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for $k$-uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972.

12 pages, 1 figure