Erdős #183 — growth rate of the k-colour triangle Ramsey number

Statement

Let $R(3;k)$ be the minimal $n$ such that if the edges of $K_n$ are coloured with $k$ colours then there must exist a monochromatic triangle. Determine \[\lim_{k\to \infty}R(3;k)^{1/k}.\] (erdosproblems.com/183, citing [Er61] Erdős, "Some unsolved problems," Magyar Tud. Akad. Mat. Kutató Int. Közl. (1961), 221-254.)

Facts

- Prize $250; status open on erdosproblems.com ("cannot be resolved with a finite computation" — it is a claim about an asymptotic growth rate). Embedded inside the same problem, Erdős separately offers $100 just for showing the limit is finite — i.e. for any proof that $R(3;k)\leq C^k$ for some constant $C$. This sub-question is *also* still open: no upper bound of exponential (or better) shape is known for $R(3;k)$ at all. - Falsifiable: no — this is an asymptotic-growth-rate statement, not decidable by any finite computation. - Origin: Erdős [Er61]. The limit is known to exist: $R(3;k)$ is supermultiplicative in $k$, so by Fekete's lemma $\lim_{k\to\infty}R(3;k)^{1/k}$ exists (possibly $+\infty$) — established via F. R. K. Chung, "On the Ramsey numbers $N(3,3,\ldots,3;2)$," Discrete Math. 5 (1973), 317-321, per mathweb.ucsd.edu/~erdosproblems/erdos/newproblems/MulticolorR3.html (the older UCSD Erdős-problems mirror of this exact problem). This existence fact is not restated on the current erdosproblems.com/183 page but is a genuine, separately-sourced result. - Known results / best bounds (verified against erdosproblems.com/183 + the underlying bibs): - Easy pigeonhole: $R(3;k)\leq 2+k(R(3;k-1)-1)$, giving $R(3;k)\leq\lceil ek!\rceil$. - Best known upper bound: $R(3;k)\leq (e-\tfrac16)k!+1$, Xu, Xie, Chen [XXC02] (2002), improving Wan [Wa97] (1997) and Whitehead [Wh73] (1973). Still factorial, not exponential. - Eliahou [El19] = arXiv:1912.05353, "An adaptive upper bound on the Ramsey numbers $R(3,\ldots,3)$" (Integers 20 (2020), A54): shows any improvement on the 4-colour value $R_4(3)=R(3,3,3,3)$ (currently known to satisfy $51\leq R_4(3)\leq 62$; conjectured $=51$) yields a better constant in the $n!$-type bound — e.g. $R_4(3)=51$ would give $R_n(3)\leq n!(e-\tfrac58)+1$. This is still a refinement of the *factorial* bound, not a route to exponential. - Best known lower bound: $R(3,k)\geq(380)^{k/5}-O(1)$ [$380^{1/5}\approx3.2806$], due to Ageron, Casteras, Pellerin, Portella, Rimmel, Tomasik [ACPPRT21] = arXiv:2112.03175 (2021), improving Exoo [Ex94] (1994) and Fredricksen–Sweet [FrSw00] (2000). Method: a "template"-based computational search for explicit sum-free partitions, giving new Schur-number lower bounds $S(9)\geq17\,803$, $S(10)\geq60\,948$, combined with the classical reduction $R(3;k)-2\geq S(k)$ and supermultiplicativity across blocks of size 5. - The central open gap: known lower bound is exponential ($\approx3.28^k$), known upper bound is factorial ($\approx(e-\tfrac16)k!$). $(k!)^{1/k}\to\infty$, so the current upper bound gives *no* finite bound on $\lim R(3;k)^{1/k}$ — the $100 sub-question is wide open on the upper-bound side. - Related problems: erdos/483 — Schur numbers $f(k)$ (an explicit "See also" link on erdosproblems.com/183); Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$ — the 2-colour diagonal Ramsey growth rate $\lim R(k)^{1/k}$, the structurally closest sibling problem (fixed *number of colours* = 2, growing *clique size* $k$, the opposite asymptotic axis from #183's fixed clique = 3, growing colour count).

Literature state

Fully open, both the $250 determine-the-limit question and the embedded $100 finiteness sub-question. No source found (erdosproblems.com remarks/forum, arXiv, OpenAlex-style web search, or the surveyed papers below) claims any resolution or even a first exponential upper bound for $R(3;k)$. The forum on erdosproblems.com/183 has no comments claiming partial progress.

Three genuinely distinct but easily-confused research lines were checked and found NOT to resolve #183:

1. List Ramsey numbers ARE resolved to be exponential — but this does not transfer. Alon, Bucić, Kalvari, Kuperwasser, Szabó, "List Ramsey numbers," arXiv:1902.07018, introduced $R_\ell(H,k)$ (every edge gets its own $k$-subset of colours from a large palette; a coloring must respect the per-edge list). Fox, He, Luo, Xu, "Multicolor list Ramsey numbers grow exponentially," arXiv:2103.15175 (I read the PDF directly), prove $R_\ell(H,k)=e^{\Theta(k)}$ for every $H$ that is not $r$-partite, in particular for $H=K_3$: $\tfrac1e\cdot2^k\lesssim R_\ell(K_3,k)\lesssim(4+o(1))^k$. Crucially, $R_\ell(H,k)\geq R(H,k)$ always (constant-list assignment is the special classical case), and the paper explicitly states: *"the same [exponential] upper bound is not even known for the classical Ramsey number $R(K_3,k)$"* — the resolved list-variant sits strictly on the wrong side of the inequality to help bound $R(3;k)$ from above. The original 2019 paper even flags a further open question for the graph case: whether $R_\ell(K_3,k)=R(K_3,k)$ is not even known to be decidable ("we cannot even decide the question of equality for cliques"). 2. The recent diagonal-Ramsey upper-bound renaissance is in the orthogonal regime. Campos, Griffiths, Morris, Sahasrabudhe, "An exponential improvement for diagonal Ramsey," arXiv:2303.09521 (2023), proved $R(k)\leq(4-\varepsilon)^k$ — the first exponential improvement to the 2-colour clique-Ramsey upper bound since Erdős–Szekeres 1935, via a new "book algorithm" density-increment induction. This was generalized to fixed-few-colours by (a) arXiv:2410.17197, "Upper bounds for multicolour Ramsey numbers": for each fixed $r\geq2$, $R_r(k)\leq e^{-\delta k}r^{rk}$ as the clique size $k\to\infty$; and (b) arXiv:2407.19026, sharpening the constant to $R(k,k)\leq3.8^{k+o(k)}$. All of these fix the number of colours and let the clique size grow — the opposite axis from #183, which fixes the clique at $K_3$ and lets the number of colours grow. No paper found applies the book-algorithm technique in the #183 direction (fixed clique, growing colours); this appears to be a genuinely unexplored transfer, not a solved-and-forgotten result. 3. A parallel, very recent (Jan 2026) lower-bound improvement line is also in the wrong regime, but its underlying inequality is regime-agnostic. Campos, Pohoata, "An update on multicolor Ramsey lower bounds," arXiv:2601.15183 (read the PDF directly), building on Conlon–Ferber, Wigderson, Sawin, and a new spherical random-geometric-graph construction of Ma–Shen–Xie, states Sawin's general inequality for all $\ell,t\geq2$: $r(t;\ell)\geq c_{t,t}^{-(\ell-2)/t}\cdot2^{(t-1)/2}$, where $c_{t,t}$ is the infimum over $K_t$-free graphs $G$ of the probability that $t$ i.i.d. uniform vertices of $G$ form an independent set. Their headline numeric result ($2^{0.3838(\ell-2)t+t/2+o(t)}$) is stated for fixed $\ell$ as $t\to\infty$ — again the wrong axis for #183 — but the underlying Theorem 1 is an exact (non-asymptotic) inequality that is formally valid at $t=3$ fixed, $\ell=k\to\infty$: $R(3;k)\geq c_{3,3}^{-(k-2)/3}\cdot2$. I did not find, and could not derive without further work, the actual numeric value of $c_{3,3}$, so I cannot say whether this beats the $380^{1/5}\approx3.2806$ base from ACPPRT21 — this is a concrete, well-posed open computation (see Attack surface). 4. A notation collision to avoid: much of the literature (e.g. arXiv:2510.19718, "Improving $R(3,k)$ in just two bites") writes "$R(3,k)$" for the 2-colour off-diagonal triangle-vs-$K_k$ Ramsey number ($\Theta(k^2/\log k)$, Kim/Bohman–Keevash regime) — a completely different object from #183's $R(3;k)$ (the $k$-colour, all-triangle multicolor Ramsey number). Confirmed by reading the arXiv:2510.19718 abstract directly.

No AI-system attempt (GPT/DeepMind/Aristotle) on #183 specifically was found in any searched source, nor on the github.com/teorth/erdosproblems tracker (not separately checked in this pass beyond the erdosproblems.com forum, which shows no relevant comment).

Attack surface

- Mode: derivation+formalization (no finite computation can resolve the asymptotic-growth-rate claim; genuine new mathematics is required for either the $250 or the $100 sub-prize). - Concrete first experiment (cheap, well-posed, not yet found in the literature): compute or bound $c_{3,3}$ — the infimum over triangle-free graphs $G$ of $\Pr[\text{3 i.i.d. uniform vertices of }G\text{ form an independent set}]$ — using the two explicit constructions from arXiv:2601.15183/[11] (Erdős–Rényi conditioned triangle-free) and arXiv:2601.15183's own spherical-random-geometric-graph refinement, specialized to $t=3$ rather than their asymptotic-in-$t$ regime. Plug into Sawin's exact inequality $R(3;k)\geq c_{3,3}^{-(k-2)/3}\cdot2$ and compare the resulting exponential base $c_{3,3}^{-1/3}$ against the current record $380^{1/5}\approx3.2806$ from ACPPRT21. Oracle: purely numeric — two explicit real numbers, mechanically comparable. - Second experiment (higher-risk, higher-reward, genuinely novel direction as far as this search found): attempt to adapt the "book algorithm" density-increment technique of Campos–Griffiths–Morris–Sahasrabudhe (arXiv:2303.09521) and its multicolour extension (arXiv:2410.17197) — currently proved only for fixed colour-count $r$ with growing clique size $k$ — to the transposed regime of #183 (fixed clique $K_3$, growing colour count $k$). This is the single most promising *named, transferable* machinery found: it is the only technique in this search that has ever produced a genuine exponential-base *improvement* to a Ramsey *upper* bound (as opposed to the century-old Erdős–Szekeres-style pigeonhole bound still used for $R(3;k)$'s upper side). No paper attempting this transfer was found. - Oracle: any candidate upper bound $R(3;k)\leq C^k$ is a genuine open-ended combinatorial/proof-theoretic claim (needs a full proof, not mechanically checkable beyond small $k$); any candidate improved lower-bound constant (route 1 above) is mechanically checkable by comparing two explicit numbers derived from stated formulas. - Feasibility: famous-and-hard for the main $250 question (a >100-year-old gap between exponential lower and factorial upper bounds, touched by some of the strongest recent combinatorics groups working on adjacent regimes without closing it). The $100 finiteness sub-question is a well-defined, high-value target: proving *any* $R(3;k)\leq C^k$ would be a genuine breakthrough. The $c_{3,3}$-numeric-comparison first experiment is realistically in reach (bounded, explicit, no proof required, just careful optimization of an existing formula) and would be a legitimate, citable contribution even if it does not resolve the problem, since erdosproblems.com does not currently record it.

Related

- erdos/483 — Schur numbers $f(k)$; #183's lower bound is derived directly from Schur-number lower bounds via $R(3;k)-2\geq S(k)$ (explicit "See also" link on erdosproblems.com/183). - Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$ — 2-colour diagonal Ramsey growth rate $\lim R(k)^{1/k}$; structurally the closest sibling (same "determine the exponential growth constant" template), but on the opposite asymptotic axis (fixed 2 colours, growing clique) — and unlike #183, its upper-bound side has seen a real breakthrough (arXiv:2303.09521). - concept/schur-numbers — sum-free partitions of $\{1,\ldots,N\}$; the combinatorial object underlying #183's best lower bound. - concept/fekete-supermultiplicative-lemma — the argument (Chung 1973) proving $\lim_{k\to\infty}R(3;k)^{1/k}$ exists at all (possibly $=\infty$), independent of determining its value. - concept/sat-based-lower-bound-search — template-graph / SAT-solver computational search technique (ACPPRT21 arXiv:2112.03175; also arXiv:2203.13476) used to push explicit Schur-number and multicolor-Ramsey lower bounds for small $k$, which then propagate via supermultiplicativity. - concept/list-ramsey-number — the list-coloring variant $R_\ell(H,k)$, proven exponential for $K_3$ (arXiv:1902.07018, arXiv:2103.15175) but structurally unable to upper-bound the classical $R(3;k)$ since $R_\ell\geq R$ always. - concept/book-algorithm-ramsey-upper-bound — the density-increment/book technique of Campos–Griffiths–Morris–Sahasrabudhe (arXiv:2303.09521) that gave the first exponential improvement to a diagonal Ramsey upper bound since 1935; not yet adapted to the fixed-clique/growing-colours regime of #183. - concept/independent-set-density-ramsey-lower-bound — the Conlon–Ferber / Wigderson / Sawin / Campos–Pohoata (arXiv:2601.15183) framework translating independent-set-density bounds $c_{t,t}$ in $K_t$-free graphs into multicolor Ramsey lower bounds $r(t;\ell)\geq c_{t,t}^{-(\ell-2)/t}2^{(t-1)/2}$, formally applicable at $t=3$ though not yet evaluated there in the literature found.