Logo
All Random Solved Random Open
SOLVED
Let $R(3,3,n)$ denote the smallest integer $m$ such that if we $3$-colour the edges of $K_m$ then there is either a monochromatic triangle in one of the first two colours or a monochromatic $K_n$ in the third colour. Define $R(3,n)$ similarly but with two colours. Show that \[\frac{R(3,3,n)}{R(3,n)}\to \infty\] as $n\to \infty$.
A problem of Erdős and Sós. This was solved by Alon and Rödl [AlRo05], who in fact show that \[R(3,3,n)\asymp n^3(\log n)^{O(1)}\] (recalling that Shearer [Sh83] showed $R(3,n) \ll n^2/\log n$).

See also the entry in the graphs problem collection.