Flashes and Rainbows in Tournaments

Colour the edges of the complete graph with vertex set \({\{1, 2, \dotsc , n\}}\) $\{1,2,\cdots ,n\}$ with an arbitrary number of colours. What is the smallest integer f(l, k) such that if \(n > f(l,k)\) $n>f(l,k)$ then there must exist a monotone monochromatic path of length l or a monotone rainbow path of length k? Lefmann, Rödl, and Thomas conjectured in 1992 that \(f(l, k) = l^{k - 1}\) $f(l,k)=l_{}^{k-1}$ and proved this for \(l \geqslant (3 k)^{2 k}\) $l⩾(3k)_{}^{2k}$ . We prove the conjecture for \(l \geqslant k^3 (\log k)^{1 + o(1)}\) $l⩾k^3(logk)_{}^{1+o(1)}$ and establish the general upper bound \(f(l, k) \leqslant k (\log k)^{1 + o(1)} \cdot l^{k - 1}\) $f(l,k)⩽k(logk)_{}^{1+o(1)}·l_{}^{k-1}$ . This reduces the gap between the best lower and upper bounds from exponential to polynomial in k. We also generalise some of these results to the tournament setting.