Determine $\lim_k R(3;k)^{1/k}$ for the multicolour triangle Ramsey number (Erdős #183)
Statement
Let $R(3;k)$ be the least $n$ such that every colouring of the edges of $K_n$ with $k$ colours contains a monochromatic triangle (a monochromatic $K_3$). Determine $$\lim_{k\to\infty} R(3;k)^{1/k}.$$ It is not even known whether this limit is finite.
Acceptance. FULLY RESOLVES: determine the limit $L=\lim_{k\to\infty} R(3;k)^{1/k}$ — either a proof that it is infinite (i.e. $R(3;k)$ grows faster than $C^k$ for every constant $C$), or a proof that it is finite and equal to a specific value with matching upper and lower bounds. Machine-checkable (Lean/Coq) preferred, otherwise a complete written proof. A proof merely that the limit is finite (that $R(3;k)\le C^k$ for some fixed $C$) is itself a headline milestone — Erdős's $100 sub-question. ADVANCES, each checkable: (a) raise the lower-bound base strictly above $380^{1/5}\approx 3.2806$ by exhibiting a new $k$-colouring of $K_n$ with no monochromatic triangle, delivered as the explicit colouring plus a machine-checkable certificate that it is triangle-free; (b) improve the upper bound strictly below $(e-\tfrac16)k!+1$ with a complete proof; (c) extend the exact values $R(3;k)$ (OEIS A003323) via a verified search plus certificate. State the improvement in words and prove it strictly beats the background. Deliver the colouring plus certificate, the code plus value plus certificate, or the proof file.
Background
Asked by Erdős [Er61]; the site records a prize of $250, and Erdős specifically offered $100 just for showing the limit is finite. An easy pigeonhole argument gives $R(3;k)\le 2+k\bigl(R(3;k-1)-1\bigr)$, from which $R(3;k)\le \lceil e\,k!\rceil$ follows. The best known upper bound is $R(3;k)\le (e-\tfrac16)k!+1$, due to Xu–Xie–Chen [XXC02] (improving Wan [Wa97] and Whitehead [Wh73]); see Eliahou [El19] for more. Because $(k!)^{1/k}\sim k/e\to\infty$, these factorial-type upper bounds do not even establish that the limit is finite. The best known lower bound, coming from multicolour Schur-number (sum-free-partition) constructions, is $R(3;k)\ge 380^{k/5}-O(1)$, due to Ageron–Casteras–Pellerin–Portella–Rimmel–Tomasik [ACPPRT21] (improving Exoo [Ex94] and Fredricksen–Sweet [FrSw00]); since $380^{1/5}\approx 3.2806$, this gives $\liminf_k R(3;k)^{1/k}\ge 3.2806$. Relevant sequence: OEIS A003323 (values $R(3;k)=R(3,3,\dots,3)$: $3,6,17,\dots$). Two venue neighbours (overlap but distinct): 'Growth of the Schur numbers $f(k)$' (Erdős #483, erdosproblems.com/483) concerns the Schur numbers whose growth base drives this lower bound, and 'Raise the lower bound for the multicolour Ramsey number $R(3,3,3,3)$ beyond 51' targets one specific small value $R(3;4)$ rather than the asymptotic base sought here. Listed as open on erdosproblems.com/183 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory. Attacker's tool: SAT / exhaustive search for better multicolour triangle-free (Schur-type) colourings to raise the lower-bound base $380^{1/5}$, and to extend exact values $R(3;k)$; analytic work to decide finiteness or to break the $k!$-type upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #183 (T. F. Bloom) | website |
| REF-02 | OEIS A003323 — multicolour Ramsey numbers R(3;k) = R(3,3,...,3) | website |
| REF-03 | Multicolour R(3) — UCSD graphs problem collection (#21, Ramsey Theory) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.