Flashes and Rainbows in Tournaments.

Colour the edges of the complete graph with vertex set { 1 , 2 , ⋯ , n } with an arbitrary number of colours. What is the smallest integer f(l, k) such that if 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 and proved this for l ⩾ (3 k) 2 k . We prove the conjecture for l ⩾ k 3 (log k) 1 + o (1) and establish the general upper bound f (l , k) ⩽ k (log k) 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. [ABSTRACT FROM AUTHOR]