Unavoidable chromatic patterns in 2-colorings of the complete graph

Abstract

We consider unavoidable chromatic patterns in $2$-colorings of the edges of the complete graph. Several such problems are explored being a junction point between Ramsey theory, extremal graph theory (Turán type problems), zero-sum Ramsey theory, and interpolation theorems in graph theory. A role-model of these problems is the following: Let $G$ be a graph with $e(G)$ edges. We say that $G$ is omnitonal if there exists a function $\mathrm{ot}(n,G)$ such that the following holds true for $n$ sufficiently large: For any $2$-coloring $f:E(K_n)\to \{red,blue\}$ such that there are more than $\mathrm{ot}(n,G)$ edges from each color, and for any pair of non-negative integers $r$ and $b$ with $r+b=e(G)$, there is a copy of $G$ in $K_n$ with exactly $r$ red edges and $b$ blue edges. We give a structural characterization of omnitonal graphs from which we deduce that omnitonal graphs are, in particular, bipartite graphs, and prove further that, for an omnitonal graph $G$, $\mathrm{ot}(n,G)=\mathcal{O}(n^{2-\frac{1}{m}})$, where $m=m(G)$ depends only on $G$. We also present a class of graphs for which $\mathrm{ot}(n,G)=ex(n,G)$, the celebrated Turán numbers. Many more results and problems of similar flavor are presented.

27 pages