Colored Unavoidable Patterns and Balanceable Graphs

We study a Turán-type problem on edge-colored complete graphs. We show that for any r and t, any sufficiently large r-edge-colored complete graph on n vertices with Ω(n2-1/trʳ) edges in each color contains a member from certain finite family Fₜʳ of r-edge-colored complete graphs. We conjecture that Ω(n2-1/t) edges in each color are sufficient to find a member from Fₜʳ. A result of Girão and Narayanan confirms this conjecture when $r=2$. Next, we study a related problem where the corresponding Turán threshold is linear. We call an edge-coloring of a path Pᵣₖ balanced if each color appears k times in the coloring. We show that any $3$-edge-coloring of a large complete graph with $kn+o(n)$ edges in each color contains a balanced P₃ₖ. This is tight up to a constant factor of $2$. For more colors, the problem becomes surprisingly more delicate. Already for $r=7$, we show that even n²⁻ᵒ⁽¹⁾ edges from each color does not guarantee existence of a balanced P₇ₖ.