Finding unavoidable colorful patterns in multicolored graphs (Q2205113)

Summary: 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\,\varepsilon\)-balanced if all color classes have \(\varepsilon\) fraction of the edges. Fix some graph \(H\), together with an \(r\)-coloring of its edges. Consider the smallest natural number \(R_\varepsilon^r(H)\) such that for all \(n\geqslant R_\varepsilon^r(H)\), all \(\varepsilon\)-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_\varepsilon^2(H)\) is finite, which was later proved by \textit{J. Cutler} and \textit{B. Montágh} [Discrete Math. 308, No. 19, 4396--4413 (2008; Zbl 1157.05039)]. 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.