Erdős #564 — is $R_3(n) \\geq 2^{2^{cn}}$? (3-uniform hypergraph Ramsey)

Statement

Let $R_3(n)$ be the minimal $m$ such that if the edges of the complete $3$-uniform hypergraph on $m$ vertices are $2$-coloured, there is a monochromatic copy of the complete $3$-uniform hypergraph on $n$ vertices. Is there a constant $c>0$ such that $$R_3(n) \geq 2^{2^{cn}}?$$ (erdosproblems.com/564, direct fetch.)

Facts

- Prize \$500; status open, falsifiability not-finite — the site states explicitly "This is open, and cannot be resolved with a finite computation" (erdosproblems.com/564, page last edited 18 January 2026). - Falsifiable: no. This is an asymptotic-growth-rate question about a function of $n\to\infty$; no single finite hypergraph coloring can settle it either way. A genuine proof (construction + argument, or a matching improved upper bound disproving it) is required. - Origin: [EHR65] Erdős, Hajnal, Rado, "Partition relations for cardinal numbers," Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196 (MR 202613) — restated by Erdős in [Er81] "On the combinatorial problems which I would most like to see solved," Combinatorica 1 (1981), 25–42, and [Er97c] "Some of my favorite problems and results" (1997). All four bib entries fetched directly from erdosproblems.com/bibs/{EHR65,Er81,Er97c,EHMR84}. - Known results / best bounds (still current as of my July-2026 search — no improvement found anywhere in the 1965–2026 literature for the plain 2-colour diagonal case): $$2^{c_1 n^2} < R_3(n) < 2^{2^{c_2 n}},$$ due to Erdős, Hajnal, Rado [EHR65] (erdosproblems.com/564). An independent reproof of the lower bound was given by Conlon, Fox, Sudakov, "Hypergraph Ramsey numbers," J. Amer. Math. Soc. 23 (2010), 247–266 (arXiv:0808.3760), who show $r_3(s,n) \geq 2^{c_1 sn\log(n/s)}$ for $4\le s\le c_2n$, which at $s=n$ recovers $2^{cn^2}$. - With 4 colours the analogous bound IS known: Erdős and Hajnal (see Graham–Rothschild–Spencer, *Ramsey Theory*, 2nd ed., cited via Mubayi–Suk survey p.2) showed $r_3(n;4) > 2^{2^{cn}}$ — a genuine double-exponential lower bound, but it needs 4 colours, not 2. - With 3 colours, the best known lower bound is $r_3(n;3) > 2^{n^{c\log n}}$ (Conlon–Fox–Sudakov 2010, arXiv:0808.3760) — still short of double-exponential. - Erdős, Hajnal, Máté, Rado [EHMR84] proved a doubly-exponential lower bound for the analogous 4-uniform, 4-colour problem. - Crucial reduction: a double-exponential lower bound for $R_3(n)$ (i.e. resolving #564 affirmatively) would, via the Erdős–Hajnal stepping-up lemma, settle the general Erdős–Hajnal–Rado tower-growth conjecture for all $k\geq 4$ uniformity simultaneously (Mubayi–Suk survey, arXiv:1707.04229, §3, explicit statement: "the crucial case is when $k=3$"). - Mubayi–Suk (arXiv:1707.04229, same paper) prove an equivalence: determining the tower growth rate of $r_3(n,n)$ (i.e. #564) is equivalent to determining the tower growth rate of the tight-path-vs-clique off-diagonal number $r_3(P_4,n)$ (general statement: $r_k(P_{k+1},n)$ vs $r_k(n,n)$ for all $k$). - Mubayi–Suk, "Off-diagonal hypergraph Ramsey numbers" (cited as [81] in the survey, submitted) show that a positive solution of #564 (Conjecture 3.1) implies a positive solution of $r_4(5,n) > 2^{2^{n^c}}$ (their "Conjecture 4.2"), i.e. #564 is upstream of that off-diagonal problem, not equivalent to it. - Related problems: Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open) — the general $r$-uniform hypergraph Ramsey tower-conjecture ($\log_{r-1}R_r(n)\asymp_r n$ for all $r\ge3$); erdosproblems.com/562 (direct fetch) confirms #564 is explicitly the $r=3$ special case. #564 is also listed as "#37 in Ramsey Theory" in the UCSD Erdős problems collection (mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/ThreeHypergraphRamsey.html, linked from erdosproblems.com/564).

Literature state

Not resolved anywhere. This is one of the oldest and most-cited open problems in hypergraph Ramsey theory (posed 1965, restated by Erdős at least twice, \$500 prize). Confirmed open by three independent checks: (1) erdosproblems.com/564 itself, last edited 18 January 2026, "0 comments," problem-status widget shows "None — there are no solutions, partial or complete, claimed"; (2) github.com/teorth/erdosproblems raw data/problems.yaml entry number: "564", status.state: "open", last_update: "2025-08-31"; (3) the Mubayi–Suk 2018 survey (arXiv:1707.04229) calls it "a notoriously difficult conjecture" and its own "Conjecture 3.1," with the gap $2^{cn^2}$ vs $2^{2^{cn}}$ explicitly still open as of the paper's last revision (May 2018) and unchanged through my July-2026 search — no arXiv paper 2018–2026 closes or narrows this specific gap for the plain 2-colour diagonal case.

Directly relevant recent literature: - Equivalence reformulation: Mubayi & Suk (arXiv:1707.04229) prove $r_3(n,n)\ge 2^{2^{cn}}$ (i.e. #564) holds iff the tight-path-vs-clique number $r_3(P_4,n) \ge 2^{2^{cn}}$ — a genuinely different, possibly more tractable combinatorial object (paths are more structured than cliques) that is provably equivalent in growth rate. - Evidence the conjecture might be FALSE: the survey explicitly flags this ("There is some evidence that perhaps Conjecture 3.1 is false") and cites two papers: Conlon–Fox–Sudakov, "Large almost monochromatic subsets in hypergraphs," Israel J. Math. 181 (2011), 423–432 (arXiv:0901.3912) — shows every $\ell$-colouring of triples of an $N$-set contains an $\Omega(\sqrt{\log N})$-size subset that is $(1-\varepsilon)$-monochromatic, a discrepancy result answering an Erdős–Hajnal 1989 question, tight up to constants; and Conlon–Fox–Rödl, "Hedgehogs are not colour blind," J. Combin. 8 (2017), 475–485 (arXiv:1511.00563) — exhibits a 3-uniform hypergraph family whose 2-colour Ramsey number is polynomial in $n$ while its 4-colour Ramsey number is exponential, the first strong colour-count dependence found in hypergraph Ramsey numbers. This undercuts the main heuristic FOR #564 (i.e. "4 colours give double-exponential, so 2 colours plausibly do too" — see the $r_3(n;4)$ fact above), since colour-count can change growth-rate class entirely. - A closely-linked off-diagonal sibling problem was just fully solved, independently of #564 (fresh 2026 result, discovered during this search): Du, Hu, Liu, Wang, "A double-exponential lower bound for $r_4(5,n)$," arXiv:2604.23986 (27 Apr 2026), prove $r_4(5,n)\ge 2^{2^{cn^{1/7}}}$ — the first double-exponential lower bound for this number, which completes the Erdős–Hajnal 1972 off-diagonal tower-growth-rate program (a *different*, 1972 conjecture, not the 1965 Erdős–Hajnal–Rado conjecture that is #564) for all fixed $k<s$. This was improved five days later in the exponent by Fan, Li, Lin, Ning, "An improved double-exponential lower bound for $r_4(5,n)$," arXiv:2605.04105 (4 May 2026), to $r_4(5,n)\ge 2^{2^{cn^{1/5}}}$, via "modifying [the] construction and reducing the greedy selection of local maxima from seven layers to five." Note the logical direction: Mubayi–Suk showed #564 $\Rightarrow$ (double-exp for $r_4(5,n)$), not the converse, so this breakthrough does not resolve #564 — but it is a live, independent construction technique (iterative/greedy "local maxima" selection + a stepping-up variant) attacking the closest solved relative of #564, worth reading for transferable ideas. - Penultimate case of the related 1972 Erdős–Hajnal conjecture solved in 2020: Mubayi, Suk, Zhu, "A note on the Erdős–Hajnal hypergraph Ramsey problem," arXiv:2003.00074, construct a 5-uniform hypergraph on $2^{2^{cn^{1/4}}}$ vertices with independence number $\le n$ and a bounded local-edge-density condition, sharp, resolving the "penultimate open case" of Erdős–Hajnal 1972 — again a sibling conjecture, not #564 itself, but same toolkit (stepping-up + explicit sharp constructions). - No AI-assisted or computational progress found: #564 does not appear in github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems (checked directly, 678-line page, no "564" match) nor in the closed GitHub issue #221 "Attacking open problems by advanced LLMs" (checked all comments, no mention). The problem statement itself IS formalized in Lean — google-deepmind/formal-conjectures FormalConjectures/ErdosProblems/564.lean exists (linked from erdosproblems.com/564) — but formalizing the *statement* is not progress toward a *proof*; data/problems.yaml confirms formalized.state: "yes", status.state: "open" (i.e. unproved).

Attack surface

- Mode: literature-resolution first (confirmed genuinely open, 60 years, no known finite reduction) with a derivation angle via the Mubayi–Suk equivalence and the freshly-solved off-diagonal sibling. - Concrete first experiment: not amenable to finite/SAT-style search (site flag: "cannot be resolved with a finite computation," and the statement is a $\Theta$-type asymptotic claim). Two concrete, runnable directions instead: (1) read arXiv:2604.23986 and arXiv:2605.04105 section-by-section and extract the exact "greedy selection of local maxima" / stepping-up-variant construction they use for $r_4(5,n)$; check mechanically (by writing out the construction on small parameters, e.g. simulate the coloring rule for $n\le 6$–$8$ in Python) whether an analogous *direct* 2-colour, 3-uniform construction (not routed through the $k=4$ case) can be built — this is the most promising concrete derivation lead surfaced by this search. (2) Read the Mubayi–Suk (arXiv:1707.04229) proof of the $r_3(n,n)\Leftrightarrow r_3(P_4,n)$ equivalence in full and check whether tight-path Ramsey numbers (which have more combinatorial structure — ordered / interval structure — than clique Ramsey numbers) admit an explicit double-exponential lower-bound construction via known tight-path-specific tools (e.g. shift graphs, Duffus–Lefmann–Rödl arXiv references in the survey bibliography, ref [35]). - Oracle: no finite oracle exists for the asymptotic claim itself. A *candidate lower-bound construction* (a family of colorings, parameterized by $n$) can be partially sanity-checked mechanically: verify computationally (brute force or SAT) that the construction, instantiated for small $n$, avoids a monochromatic $K_n^{(3)}$ on the claimed number of vertices — this only checks the base cases, not the asymptotic rate, but catches off-by-construction errors early. A full proof would need to go through peer review / Lean formalization against the existing formal-conjectures stub. - Feasibility: low for the headline \$500 result itself — this is a 60-year-old, heavily-studied central problem in hypergraph Ramsey theory (explicitly called "notoriously difficult" and "the crucial case" by the standard survey), attacked by Erdős, Hajnal, Rado, Conlon, Fox, Sudakov, Mubayi, Suk and others with no improvement to the $2^{cn^2}$ vs $2^{2^{cn}}$ gap since 1965/2010. There is also live expert suspicion the conjecture is FALSE (Conlon–Fox–Rödl hedgehog result). Medium feasibility for a genuine *derivation* contribution: the field is moving fast right now on the closest sibling problem ($r_4(5,n)$, 3 papers Oct-2024/Apr-2026/May-2026), so reading those very recent constructions and testing whether their "local maxima" technique transfers directly to the 2-colour diagonal case is a well-defined, currently-active research direction, not a stale one.

Related

- Erdős #562 — Erdős–Hajnal–Rado hypergraph Ramsey growth rate: SOLVED at the ≥4-colour endpoint via the stepping-up lemma (2-colour case still open) — the general $r$-uniform hypergraph Ramsey tower-growth conjecture that #564 is the crucial $r=3$, 2-colour special case of; resolving #564 affirmatively settles #562 for all $r\ge4$ via the stepping-up lemma. - concept/stepping-up-lemma — Erdős–Hajnal's technique for lifting a $k$-uniform Ramsey lower bound to a $(k+1)$-uniform one with one extra tower level; the reason $k=3$ is "the crucial case" for the whole tower-growth conjecture family. - concept/hypergraph-ramsey-numbers — the general $r_k(s,n)$ framework (Mubayi–Suk survey, arXiv:1707.04229) this problem lives in. - concept/tower-function-growth-rate — the $\mathrm{twr}_k(x)$ tower-height bookkeeping used throughout hypergraph Ramsey theory to state and compare conjectures like #564. - concept/probabilistic-deletion-construction — the technique behind the current best known $2^{cn^2}$ lower bound (Erdős–Hajnal–Rado 1965; reproved by Conlon–Fox–Sudakov 2010, arXiv:0808.3760). - concept/tight-path-ramsey-number — the $r_k(P_{k+1},n)$ object Mubayi–Suk (arXiv:1707.04229) prove is growth-rate-equivalent to #564; a promising alternate combinatorial target with more exploitable structure. - concept/multicolour-ramsey-discrepancy — the Conlon–Fox–Sudakov (arXiv:0901.3912) and Conlon–Fox–Rödl (arXiv:1511.00563, "hedgehogs") results on how hypergraph Ramsey growth rate depends sharply on the number of colours, cited as evidence #564 could be false. - Du–Hu–Liu–Wang (Apr 2026), improved by Fan–Li–Lin–Ning (May 2026) — a double-exponential lower bound for $r_4(5,n)$, completing the Erdős–Hajnal 1972 off-diagonal hypergraph-Ramsey tower-growth-rate program — Du–Hu–Liu–Wang (arXiv:2604.23986, Apr 2026), improved by Fan–Li–Lin–Ning (arXiv:2605.04105, May 2026): closest live solved sibling problem, upstream-implied-by #564 but solved independently via a fresh "greedy local maxima" construction technique worth mining.