Chromatic Ramsey numbers and two-color Tur\'{a}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 $\pi^{(2)}(G)=\lim_{n\to\infty}\mathrm{ex}^{(2)}(n,G)/\binom{n}{2}$ 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 $\pi^{(2)}(G)=1-(R_{\chi}(G)-1)^{-1}$, where $R_{\chi}(G)$ is the chromatic Ramsey number of $G$.
Burr, Erdős, and Lovász showed that $(k-1)^2+1\leq{R_{\chi}(G)}\leq{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_{\chi}(G)$ of some $k$-chromatic graph $G$ for general $k$.
In this paper, among others, we prove that there are $\Omega(k)$ different values of $R_{\chi}(G)$ among $k$-chromatic graphs $G$.
This sheds more light onto the possible $2$-color Turán densities of graphs.