Colored unavoidable patterns and balanceable graphs

Matt Bowen, Adriana Hansberg, Amanda Montejano, Alp Müyesser

Published 2019-12-13Version 1

We study a Tur\'an-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 $\Omega(n^{2-\frac{1}{t}})$ edges in each color contains an $(r,t)$-unavoidable graph, where an $(r,t)$-unavoidable graph is essentially a $t$-blow-up of an $r$-colored complete graph where all $r$ colors are present. The result is tight up to the implied constant factor, assuming the well-known conjecture that $ex(K_{t,t})=\Theta(n^{2-{1/t}})$. Next, we study a related problem where the corresponding Tur\'an threshold is linear. In particular, we show that any $3$-edge-coloring of a large enough complete graph with $kn+o(n)$ edges in each color contains a path on $3k$ edges with an equal number of edges from each color. This is tight up to a constant factor of $2$.