For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge coloring of the complete graph on n vertices (with any number of colors) has a monochromatic subgraph isomorphic to S or a rainbow subgraph isomorphic to T. Here, a subgraph is said to be rainbow if all of its edges have different colors. It is an immediate consequence of the Erdös-Rado Canonical Ramsey Theorem that f(S, T) exists if and only if S is a star or T is acyclic. Much work has been done to determine the rate of growth of f(S, T) for various types of parameters. When S and T are both trees having s and t edges respectively, Jamison, Jiang, and Ling showed that f(S, T) ≤ O(st2) and conjectured that it is always at most O(st). They also mentioned that one of the most interesting open special cases is when T is a path. We study this case and show that f(S, Pt) = O(st log t), which differs only by a logarithmic factor from the conjecture. This substantially improves the previous bounds for most values of s and t.
Joint work with Benny Sudakov.