Finding unavoidable colorful patterns in multicolored graphs

Abstract

We provide multicolored and infinite generalizations for a Ramsey-type problem raised by Bollobás, concerning colorings of $K_n$ where each color is well-represented. Let $\chi$ be a coloring of the edges of a complete graph on $n$ vertices into $r$ colors. We call $\chi$ $\epsilon$-balanced if all color classes have $\epsilon$ fraction of the edges. Fix some graph $H$, together with an $r$-coloring of its edges. Consider the smallest natural number $R_{\epsilon }^r(H)$ such that for all $n\ge R_{\epsilon }^r(H)$, all $\epsilon$-balanced colorings $\chi$ of $K_n$ contain a subgraph isomorphic to $H$ in its coloring. Bollobás conjectured a simple characterization of $H$ for which $R_{\epsilon }^2(H)$ is finite, which was later proved by Cutler and Montágh. Here, we obtain a characterization for arbitrary values of $r$, as well as asymptotically tight bounds. We also discuss generalizations to graphs defined on perfect Polish spaces, where the corresponding notion of balancedness is each color class being non-meagre.