A step forwards on the Erdős-Sós problem concerning the Ramsey numbers $R(3,k)$

Abstract

Let ${\Delta }_s=R(K_3,K_s)-R(K_3,K_{s-1})$, where $R(G,H)$ is the Ramsey number of graphs $G$ and $H$ defined as the smallest $n$ such that any edge coloring of $K_n$ with two colors contains $G$ in the first color or $H$ in the second color. In 1980, Erdős and Sós posed some questions about the growth of ${\Delta }_s$. The best known concrete bounds on ${\Delta }_s$ are $3\le {\Delta }_s\le s$, and they have not improved since the stating of the problem. In this paper we present some constructions, which imply in particular that $R(K_3,K_s)\ge R(K_3,K_{s-1}-e)+4$. This does not improve the lower bound of 3 on ${\Delta }_s$, but we still consider it a step towards to understanding its growth. We discuss some related questions and state two conjectures involving ${\Delta }_s$, including the following: for some constant $d$ and all $s$ it holds that ${\Delta }_s-{\Delta }_{s+1}\le d$. We also prove that if the latter is true, then ${\lim }_{s\to \infty }{\Delta }_s/s=0$.

10 pages