Problem 564

Let $R_3(n)$ be the minimal $m$ such that if the edges of the $3$ -uniform hypergraph on $m$ vertices are $2$ -coloured then there is a monochromatic copy of the complete $3$ -uniform hypergraph on $n$ vertices.

Is there some constant $c>0$ such that

R_3(n) \geq 2^{2^{cn}}?

Source: erdosproblems.com/564

Graph theory
Ramsey theory
Hypergraphs

Wiki page

Status

Open

No claim settles this problem.

Open. No proof, disproof, preprint or proof claim for the exact statement was found in the search whose scope the Current assessment records. The bounds in hand are $2^{cn^2}\le R_3(n)\le2^{2^{4n-10}}$ , both stated in [EHR65] with the proofs omitted; the double-exponential lower bound is known with four colors, and a 2025 paper published in 2026 calls closing the two-color gap "a major open problem". This is a bounded negative finding, not a certificate of openness.

EHR65: Erdős, P., Hajnal, A. and Rado, R., Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar. 16 (1965), no. 1--2, 93--196, doi:10.1007/BF01886396; Section 16, printed pp. 139--140. Library home: Erdős and Rado 1965.
EHMR84: Erdős, P., Hajnal, A., Máté, A. and Rado, R., Combinatorial set theory: partition relations for cardinals. Studies in Logic and the Foundations of Mathematics 106, North-Holland (1984), 347 pp. Not held; not consulted.
BHS25: Bradač, D., Hunter, Z. and Sudakov, B., Lower bounds for Ramsey numbers of bounded degree hypergraphs. J. Combin. Theory Ser. B 179 (2026), 250--269, doi:10.1016/j.jctb.2026.04.002; arXiv:2502.20863 (v1 28 February 2025; v3 15 August 2025). Library home: Bradač and Sudakov 2025.
ErRa52: Erdős, P. and Rado, R., Combinatorial theorems on classifications of subsets of a given set. Proc. London Math. Soc. (3) 2 (1952), 417--439. The source [EHR65] cites for the upper bound 16.3; not held; context.
Er47: Erdős, P., Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 (1947), 292--294. The source [EHR65] cites for 16.2 and, "without detailed proof", for the lower bound 16.4; not held; context.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), 25--42. Site source key; Part V, pp. 9--10 of the Rényi archive's re-typeset copy, a problem of Hajnal, Rado and Erdős posed as display (5) on p. 10: "Is it true that (5) $\log\log r(K^{(3)}(n),K^{(3)}(n))>cn$ ? In other words, does $r(K^{(3)}(n),K^{(3)}(n))$ tend to infinity like a double exponential. This question is fundamental and I offer 500 dollars for a proof or disproof of (5)." Library home: Erdős 1981.
Er97c: Erdős, P., Some of my favorite problems and results. The mathematics of Paul Erdős, I, Algorithms Combin. 13, Springer (1997), 47--67; display (4.3) and its discussion, printed p. 63. Library home: Erdős 1997; paged at Erdős 1997, Display (4.3).

Problem 564

Status

Proof claims

Discussion