Finding unavoidable colorful patterns in multicolored graphs

Matt Bowen¹ ; Ander Lamaison² ; Alp Müyesser¹

¹Carnegie Mellon University
²Freie Universitat

The electronic journal of combinatorics, Tome 27 (2020) no. 4

Résumé

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\geq 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 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.

Détail

DOI : 10.37236/8184

Classification : 05D10, 05D40, 05C55
Mots-clés : Ramsey-type problem