Turán‐ and Ramsey‐type results for unavoidable subgraphs.

We study Turán‐ and Ramsey‐type problems on edge‐colored graphs. A two‐edge‐colored graph is called ε $\varepsilon $‐balanced if each color class contains at least an ε $\varepsilon $‐proportion of its edges. Given a family F ${\rm{ {\mathcal F} }}$ of two‐edge‐colored graphs, the Ramsey‐type function R(ε,F) $R(\varepsilon ,{\rm{ {\mathcal F} }})$ is the smallest n $n$ for which any ε $\varepsilon $‐balanced Kn ${K}_{n}$ must contain a copy of an F∈F $F\in {\rm{ {\mathcal F} }}$, and the Turán‐type function ex(ε,n,F) $\text{ex}(\varepsilon ,n,{\rm{ {\mathcal F} }})$ is the maximum number of edges in an n $n$‐vertex ε $\varepsilon $‐balanced graph which avoids all of F ${\rm{ {\mathcal F} }}$. In this paper, we show that for any ε′<ε≤1∕2 $\varepsilon ^{\prime} \lt \varepsilon \le 1\unicode{x02215}2$, ex(ε,n,F)∕n2≤1−Ω(1∕R(ε′,F)) $\text{ex}(\varepsilon ,n,{\rm{ {\mathcal F} }})\unicode{x02215}\left(\genfrac{}{}{0.0pt}{}{n}{2}\right)\le 1-{\rm{\Omega }}(1\unicode{x02215}R(\varepsilon ^{\prime} ,{\rm{ {\mathcal F} }}))$, as long as R(ε′,F) $R(\varepsilon ^{\prime} ,{\rm{ {\mathcal F} }})$ is finite. We use this result to show that the Ramsey‐type function is linear for bounded degree graphs. Finally, we consider the Turán‐type function for several classes of edge‐colored graphs. In particular, we show that for any k $k$, sufficiently large (1∕2) $(1\unicode{x02215}2)$‐balanced graphs with edge‐density above 1/2 must contain a k $k$‐cycle with a non‐monochromatic coloring of its edge set. The same result when k=3 $k=3$ was proved by DeVos, McDonald, and Montejano. [ABSTRACT FROM AUTHOR]