Chromatic Ramsey numbers and two-color Turán densities

Abstract

Given a graph $G$, its $2$-color Turán number ${\mathrm{ex}}^{(2)}(n,G)$ is the maximum number of edges in an $n$-vertex graph, such that the edges can be colored with two colors avoiding a monochromatic copy of $G$. Let $\ddot{I}{€}^{(2)}(G)={\lim }_{n\to \infty }{\mathrm{ex}}^{(2)}(n,G)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ be the $2$-color Turán density of $G$. What real numbers in the interval $(0,1)$ are realized as the $2$-color Turán density of some graph? It is known that $\ddot{I}{€}^{(2)}(G)=1-(R_{\ddot{I}}‡(G)-1{)}^{-1}$, where $R_{\ddot{I}}‡(G)$ is the chromatic Ramsey number of $G$. Burr, Erdős, and Lovász showed that $(k-1{)}^2+1\le R_{\ddot{I}}‡(G)\le R(k)$, for any $k$-chromatic graph $G$, where $R(k)$ is the classical Ramsey number. However, it is an open problem to determine how many distinct values between $(k-1{)}^2+1$ and $R(k)$ can be realized as $R_{\ddot{I}}‡(G)$ of some $k$-chromatic graph $G$ for general $k$. In this paper, among others, we prove that there are $\hat{I}\text{c◯}(k)$ different values of $R_{\ddot{I}}‡(G)$ among $k$-chromatic graphs $G$. This sheds more light onto the possible $2$-color Turán densities of graphs.

14 pages, 3 figures