# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/564.lean).

## 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](https://doi.org/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](https://doi.org/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](https://doi.org/10.1090/S0894-0347-09-00645-6)

## Source

Imported from [Erdős Problems 564](https://www.erdosproblems.com/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.