2023/05/22 by Girão, António, Illingworth, Freddie, Michel, Lukas +2 · 1 citation
#05C35 #05C38 #05C55 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2305.13422
Colour the edges of the complete graph with vertex set \1, 2, \dotsc, 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) = lk - 1 and proved this for l ≥ (3 k)2 k. We prove the conjecture for l ≥ k3 (log k)1 + o(1) and establish the general upper bound f(l, k) ≤ k (log k)1 + o(1) ⋅ lk - 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.