Flashes and rainbows in tournaments

Abstract

Colour the edges of the complete graph with vertex set $\{1,2,\dots ,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\ge (3k{)}^{2k}$. We prove the conjecture for $l\ge k^3(\log k{)}^{1+o(1)}$ and establish the general upper bound $f(l,k)\le k(\log k{)}^{1+o(1)}\cdot 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.

14 pages, improved Theorem 1.3 slightly