Doubly exponential growth of 3-uniform Ramsey numbers

Colour every triple of an $m$-element set red or blue: how large must $m$ be to guarantee $n$ points whose triples all have the same colour? The answer lies between $2^{cn^2}$ and $2^{2^n}$, an enormous gap. Erdős, Hajnal and Rado conjectured that the truth is doubly exponential, and Erdős offered $500 for a proof.

Problem

Let $R_3(n)$ be the least $m$ such that in every 2-colouring of the triples of an $m$-element set there are $n$ elements all of whose $\binom n3$ triples have the same colour. Is there a constant $c>0$ such that

$$R_3(n)\ge 2^{2^{cn}}\quad\text{for all large } n\,?$$

Background

For graphs, the Ramsey number $R(n)$ grows exponentially in $n$. For triples, Erdős, Hajnal and Rado (1965) proved

$$2^{cn^2}<R_3(n)<2^{2^{n}}$$

for a constant $c>0$. The lower bound comes from a random colouring, and no better construction is known for two colours. The question is a special case of the general problem of how fast hypergraph Ramsey numbers grow, and it is the key case: the Erdős–Hajnal stepping-up lemma turns lower bounds for $3$-uniform hypergraphs into lower bounds one exponential higher for each further uniformity. A doubly exponential lower bound for $R_3(n)$ would therefore give lower bounds for every uniformity $k\ge3$ that match the known upper bounds, a tower of height $k$, up to the constant in the top exponent. Erdős listed it among the combinatorial problems he most wanted to see solved.

What is known

• Two colours. The bounds $2^{cn^2}<R_3(n)<2^{2^n}$ of Erdős, Hajnal and Rado (1965) remain the best known.
• Four colours. Erdős, Hajnal, Máté and Rado (1984) proved a doubly exponential lower bound when the triples are coloured with four colours.
• Three colours. Conlon, Fox and Sudakov (2010) improved an old result of Erdős and Hajnal, showing that the 3-colour Ramsey number of triples is at least $2^{n^{c\log n}}$.
• Off-diagonal numbers. Conlon, Fox and Sudakov also proved the first superexponential lower bound for $r_3(s,n)$ with $s\ge4$ fixed, answering a question of Erdős and Hajnal from 1972.

What would count as progress

• A 2-colouring of the triples of a set of size $2^{2^{cn}}$ (or even $2^{n^{2+\delta}}$) with no monochromatic set of size $n$, given as an explicit or randomised construction with a proof; small cases can be checked by computer.
• A proof that $R_3(n)\le 2^{2^{o(n)}}$, which would disprove the conjecture.
• A doubly exponential lower bound for three colours.
• A formal proof against the Lean statement in formal-conjectures.

References

1. P. Erdős, A. Hajnal and R. Rado, Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196. doi:10.1007/BF01886396
2. P. Erdős, On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25–42. doi:10.1007/BF02579174
3. D. Conlon, J. Fox and B. Sudakov, Hypergraph Ramsey numbers, J. Amer. Math. Soc. 23 (2010), 247–266. doi:10.1090/S0894-0347-09-00645-6

Source

Imported from Erdős Problems 564, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.