pith. sign in

arxiv: 2409.07535 · v2 · pith:2KUJWMSQnew · submitted 2024-09-11 · 🧮 math.CO

Chromatic Ramsey numbers and two-color Tur\'{a}n densities

classification 🧮 math.CO
keywords chromaticgraphcolornumberramseydensitiesdensityedges
0
0 comments X
read the original abstract

Given a graph $G$, its $2$-color Tur\'{a}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\'{a}n density of $G$. What real numbers in the interval $(0,1)$ are realized as the $2$-color Tur\'{a}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\H{o}s, and Lov\'{a}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\'{a}n densities of graphs.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.