All Random Solved Random Open
OPEN - $250
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}.\]
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 due to Exoo [Ex94], \[R(3;k) \gg (321)^{k/5}.\]

See also [483].

See also the entry in the graphs problem collection.

Additional thanks to: Antonio Girao, David Penman