Problem 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}.\]
Categories:
Graph Theory Ramsey Theory
Progress
Erdős offers \$100 for showing that this limit is finite. An easy pigeonhole argument shows that\[R(3;k)\leq 2+k(R(3;k-1)-1),\]from which $R(3;k)\leq \lceil e k!\rceil$ immediately follows. The best-known upper bounds are all of the form $ck!+O(1)$, and arise from this type of inductive relationship and computational bounds for $R(3;k)$ for small $k$. The best-known lower bound (coming from lower bounds for Schur numbers) is\[R(3,k)\geq (380)^{k/5}-O(1),\]due to Ageron, Casteras, Pellerin, Portella, Rimmel, and Tomasik [ACPPRT21] (improving previous bounds of Exoo [Ex94] and Fredricksen and Sweet [FrSw00]). Note that $380^{1/5}\approx 3.2806$.See also [483].
This problem is #21 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/183 | Last verified: January 14, 2026