The Erdős–Hajnal hypergraph Ramsey problem

  • Dhruv Mubayi

    University of Illinois at Chicago, USA
  • Andrew Suk

    University of Illinois at Chicago, USA
The Erdős–Hajnal hypergraph Ramsey problem cover

A subscription is required to access this article.


Given integers , let be the minimum such that every red/blue coloring of the -subsets of yields either a -set containing red -subsets, or an -set with all of its -subsets blue. Erdős and Hajnal proved in 1972 that for fixed , there are positive constants and such that

where is a tower of 2's of height . 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 . Here we settle the Erdő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 within the tower. Specifically, we prove that if and is even, then

Similar results are proved for odd.

Cite this article

Dhruv Mubayi, Andrew Suk, The Erdős–Hajnal hypergraph Ramsey problem. J. Eur. Math. Soc. 22 (2020), no. 4, pp. 1247–1259

DOI 10.4171/JEMS/944