Canonical Ramsey numbers of sparse graphs

The canonical Ramsey theorem of Erdős and Rado implies that for any graph 𝐻, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph 𝐾𝑁 contains a monochromatic, lexicographic, or rainbow copy of 𝐻. The least such 𝑁 is called the Erdős–Rado number of 𝐻, denoted by 𝐸⁢𝑅⁡(𝐻). Erdős–Rado numbers of cliques have received considerable attention, and in this paper we extend this line of research by studying Erdős–Rado numbers of sparse graphs. For example, we prove that if 𝐻 has bounded degree, then 𝐸⁢𝑅⁡(𝐻) is polynomial in |𝑉⁡(𝐻)| if 𝐻 is bipartite but exponential in general. We also study the closely related problem of constrained Ramsey numbers. For a given tree S and given path 𝑃𝑡, we study the minimum 𝑁 such that every edge-coloring of 𝐾𝑁 contains a monochromatic copy of S or a rainbow copy of 𝑃𝑡. We prove a nearly optimal upper bound for this problem, which differs from the best known lower bound by a function of inverse Ackermann type.