Paper detail

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

Let $Δ_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 $Δ_s$. The best known concrete bounds on $Δ_s$ are $3 \le Δ_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 $Δ_s$, but we still consider it a step towards to understanding its growth. We discuss some related questions and state two conjectures involving $Δ_s$, including the following: for some constant $d$ and all $s$ it holds that $Δ_s - Δ_{s+1} \leq d$. We also prove that if the latter is true, then $\lim_{s \rightarrow \infty} Δ_s/s=0$.