Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: A step forwards on the Erd\H{o}s-S\'os problem concerning the Ramsey
  numbers $R(3,k)$   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\H{o}s and S\'{o}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} \leq d$. We also prove that if the latter is
true, then $\lim_{s \rightarrow \infty} \Delta_s/s=0$.

34
The categories of this paper are: chem-ph
35
The categories of this paper are: mtrl-th
32
The categories of this paper are: atom-ph
30
The categories of this paper are: q-alg
21
The categories of this paper are: adap-org
25
The categories of this paper are: patt-sol
16
The categories of this paper are: stat
23
The categories of this paper are: solv-int
12
The categories of this paper are: nucl-th
3
The categories of this paper are: physics
1
The categories of this paper are: cs
28
The categories of this paper are: alg-geom
37
The categories of this paper are: supr-con
33
The categories of this paper are: plasm-ph
26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph