2018/10/29 by Caro, Yair, Hansberg, Adriana, Montejano, Amanda · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1810.12375
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 \rm ot(n,G) such that the following holds true for n sufficiently large: For any 2-coloring f: E(Kn) → \red, blue \ such that there are more than \rm 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 Kn 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, \rm ot(n,G) = O(n2 - (1)/(m)), where m = m(G) depends only on G. We also present a class of graphs for which \rm ot(n,G) = ex(n,G), the celebrated Turán numbers. Many more results and problems of similar flavor are presented.