Unavoidable subgraphs of colored graphs

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper, we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k  , let SkSk be the family of two-edge-colored graphs on k   vertices such that one of the colors forms either two disjoint Kk/2Kk/2's or simply one Kk/2Kk/2. Bollobás conjectured that for all k   and ε>0ε>0, there exists an n(k,ε)n(k,ε) such that if n⩾n(k,ε)n⩾n(k,ε) then every two-edge-coloring of KnKn, in which the density of each color is at least εε, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,ε)n(k,ε) for different ranges of εε. In particular, if εε is sufficiently close to 12, the gap between our upper and lower bounds for n(k,ε)n(k,ε) is smaller than those for the classical Ramsey number R(k,k)R(k,k).