On Canonical Ramsey Numbers for Complete Graphs versus Paths

In this note we study the following canonization type problem: Let ƒ(Pk, Kl) be the minimum number n of vertices of a complete graph Kn with totally ordered vertex set having the property that for every coloring of the edges of Kn, by an arbitrary number of colors one can always find either a totally multicolored increasing path Pk of length k or a monochromatic complete subgraph Kl. We show that this number is related to the classical Ramsey number rk−1(l) (i.e., the least positive integer m such that for any (k − 1)-coloring of the edges of Km, there is a monochromatic Kl). We prove that ƒ(P3, Kl) = r2(l) + r1(l) for l ≥ 5 and give a lower bound for ƒ(Pk, Kl) in terms of properties of classical Ramsey graphs. We also consider Erdős-Rado canonization numbers er(k) defined analogously as Ramsey numbers. Improving an earlier lower bound painted out by F. Galvin and an upper bound which follows from the proof of P. Erdős and R. Rado we show that 2ck2 ≤ er(k) ≤ 22c′k3.