Problem 562

Let $R_r(n)$ denote the $r$ -uniform hypergraph Ramsey number: the minimal $m$ such that if we $2$ -colour all edges of the complete $r$ -uniform hypergraph on $m$ vertices then there must be some monochromatic copy of the complete $r$ -uniform hypergraph on $n$ vertices.

Prove that, for $r\geq 3$ ,

\log_{r-1} R_r(n) \asymp_r n,

where $\log_{r-1}$ denotes the $(r-1)$ -fold iterated logarithm. That is, does $R_r(n)$ grow like

2^{2^{\cdots n}}

where the tower of exponentials has height $r-1$ ?

Source: erdosproblems.com/562

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. For every $r\ge3$ the bounds in hand are $\log_{r-1}R_r(n)\le k_rn$ (Erdős and Rado, stated as 16.3 of [EHR65]) and $\log_{r-1}R_r(n)\ge\log_2(c'n^2)$ (the stepping-up lower bound $R_r(n)\ge\mathrm{twr}_{r-1}(c'n^2)$ , a tower one exponentiation short, restated second-hand in 2025--2026 sources; [EHR65] states $2^{cb^2}$ for $r=3$ and, proofs omitted, $\mathrm{twr}_{r-1}(\tfrac12c^{r-3}b)$ for general $r$ ), so the lower side is known only at order $\log n$ against the conjectured order $n$ ; with four colors the matching lower bound is known ([BHS25] p. 1, crediting the Erdős--Hajnal stepping-up construction via Graham, Rothschild and Spencer; the site's Problem 564 commentary credits the 3-uniform case to Erdős, Hajnal, Máté and Rado 1984, not held), 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.
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, doi:10.1112/plms/s3-2.1.417. The source of the upper bound 16.3; not held.
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 $r=3$ lower bound 16.4; not held; context.
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). Credited by the site's Problem 564 commentary with the four-color, 3-uniform double-exponential lower bound; [BHS25] does not cite it, crediting the general four-color bound to the Erdős--Hajnal stepping-up construction via Graham, Rothschild and Spencer. Not held.
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.20863v3. Its introduction's summary of the tower bounds, p. 1. Library home: Bradač and Sudakov 2025; result page remark, p. 1.
BDHLW26: Bai, H., Du, L., Hu, X., Liu, R. and Wang, G., New tower-type lower bounds for hypergraph Ramsey numbers. arXiv:2606.24198v1 (23 June 2026), 14 pages; preprint, no journal record; its introduction's restatement of the general bounds, pp. 1--2, and Theorems 1.2--1.3. Library home: Bai 2026.
PRW26: Pudlák, P., Rödl, V. and Wesley, W. J., A lower bound on the Ramsey number $R_k(k+1,k+1)$ . Adv. Comb. 2026, Paper No. 3, doi:10.19086/aic.2026.3 (Crossref record dated 24 April 2026). Not held; known here through [BDHLW26].
CFS10: Conlon, D., Fox, J. and Sudakov, B., Hypergraph Ramsey numbers. J. Amer. Math. Soc. 23 (2010), 247--266; arXiv:0808.3760 (abstract accessed). Off-diagonal and three-color bounds; not held.
CFS13: Conlon, D., Fox, J. and Sudakov, B., An improved bound for the stepping-up lemma. Discrete Appl. Math. 161 (2013), 1191--1196; arXiv:0907.0283 (abstract accessed). Not held.
DoMu26: Dobák, D. and Mulrenin, E., Recursive upper bounds for the vertex online Ramsey game with applications to hypergraph Ramsey numbers. arXiv:2605.16607v1 (15 May 2026). Preprint; abstract only.

Problem 562

Status

Proof claims

Discussion