On canonical Ramsey numbers for complete graphs versus paths (Q1325270)

We study the following canonization type problems: Let \(f(P_ k,K_ l)\) be the minimum number \(n\) of vertices of a complete graph \(K_ n\) with totally ordered vertex set having the property that for every coloring of the edges of \(K_ n\) by an arbitrary number of colors one can always find either a totally multicolored increasing path \(P_ k\) of length \(k\) or a monochromatic complete subgraph \(K_ l\). We show that this number is related to the classical Ramsey number \(r_{k-1}(l)\) (i.e., the least positive integer \(m\) such that for any \((k-1)\)-coloring of the edges of \(K_ m\) there is a monochromatic \(K_ l\)). We prove that \(f(P_ 3,K_ l)= r_ 2(l)+ r_ 1(l)\) for \(l\geq 5\) and give a lower bound for \(f(P_ k,K_ l)\) in terms of classical Ramsey graphs. We also consider Erdős-Rado canonization numbers \(er(k)\) defined analogously as Ramsey numbers. Improving an earlier lower bound pointed out by F. Galvin and an upper bound which follows from the proof of P. Erdős and R. Rado we show that \(2^{ck^ 2}\leq er(k)\leq 2^{2^{c'k^ 3}}\). Note added in proof: Recently we improved the upper bound by showing that \(er(k)\leq 2^{ck^ 2\log k}\).