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 (n^2-1/trʳ) edges in each color contains a member from certain finite family Fₜʳ of r-edge-colored complete graphs. We conjecture that (n^2-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^2-o (1) edges from each color does not guarantee existence of a balanced P₇₊.