Ramsey numbers when each color has small chromatic number

Let $F(j,k)$ be the least $n$ such that one can color the edges of the complete graph on $n$ vertices with $k$ colors such that the graph formed from the edges of each color is triangle-free and admits a vertex $j$-coloring.

Does there exist $j$ such that $\lim_{k\to \infty} F(j,k)/j^k =0$?

Clearly $F(j,k)$ is at most the $k$-colored Ramsey number $r_3(k)$ which is defined the same way but dropping the last condition.

The recent lower bounds obtained by OpenAI on $r_3(k)$ proceed by lower bounds on $F(j,k)$ obtained by induction on $j$ (in which $k$ also increases). This motivates studying the size of $F(j,k)$. I think the above is one of the most interesting yes-or-no questions about it.

The upper bound $F(j,k)\leq j^k$ is basically trivial: the $k$ different $j$-colorings give a $j^k$-coloring of the vertices, and no two vertices can have the same color.

We have $F(j,k+1)\leq j F(j,k)$ by picking one of the $j$ colors of the last $j$-coloring and throwing out all other vertices. Combined with an upper bound for Ramsey numbers, this gives a savings over the trivial bound, but a savings that is bounded for each $j$. The question is if we can do better.

添加评论
点赞收藏
点踩分享查看原文
评论
?
参与讨论