New upper bounds for a canonical Ramsey problem (Q1586336)

Let \(f(l,k)\) be the minimum \(n\) with the property that every coloring \(c:\binom{[n+1]}2\to\{ 1,2,\dots\}\) (i.e., coloring of the edges of \(K_{n+1}\) with arbitrary many colors) yields either \(x_0<\dots<x_l\) with \(c(x_0,x_1)=\dots=c(x_{l-1},x_l)\), or \(y_0<\dots<y_k\) with \(c(y_0,y_1),\dots,c(y_{k-1},y_k)\) all distinct. In the paper it is proved that if \(k=o(\sqrt{l})\), then \(f(l,k)\sim l^{k-1}\) as \(l\to\infty\). This supports the conjecture of Lefmann, Rödl, and Thomas that \(f(l,k)=l^{k-1}\); see \textit{H. Lefmann, V. Rödl} and \textit{R. Thomas} [Graphs Comb. 8, No. 4, 323-332 (1992; Zbl 0769.05092)].