The evolution of unavoidable bi-chromatic patterns and extremal cases of balanceability

Abstract

We study the color patterns that, for $n$ sufficiently large, are unavoidable in $2$-colorings of the edges of a complete graph $K_n$ with respect to $\min \{e(R),e(B)\}$, where $e(R)$ and $e(B)$ are the numbers of red and, respectively, blue edges. More precisely, we determine how such unavoidable patterns evolve from the case without restriction in the coloring, namely that $\min \{e(R),e(B)\}\ge 0$ (given by Ramsey's theorem), to the highest possible restriction, namely that $|e(R)-e(B)|\le 1$. We also investigate the effect of forbidding certain sub-structures in each color. In particular, we show that, in $2$-colorings whose graphs induced by each of the colors are both free from an induced matching on $r$ edges, the appearance of the unavoidable patterns is already granted with a much weaker restriction on $\min \{e(R),e(B)\}$. We finish analyzing the consequences of these results to the balancing number $bal(n,G)$ of a graph $G$ (i.e. the minimum $k$ such that every $2$-edge coloring of $K_n$ with $\min \{e(R),e(B)\}>k$ contains a copy of $G$ with half the edges in each color), and show that, for every $\epsilon >0$, there are graphs $G$ with $bal(n,G)\ge c{n}^{2-\epsilon }$, which is the highest order of magnitude that is possible to achieve, as well as graphs where $bal(n,G)\le c(G)$, where $c(G)$ is a constant that depends only $G$. We characterize the latter ones.

16 pages, 2 figures