# Bounds for growth of $$r(3, n)$$

For two graphs $$G$$ and $$H$$, let $$r(G,H)$$ denote the smallest integer $$m$$ satisfying the property that if the edges of the complete graph $$K_m$$ are colored in red and blue, then there is either a subgraph isomorphic to $$G$$ with all red edges or a subgraph isomorphic to $$H$$ with all blue edges. The classical Ramsey numbers are those for the complete graphs and are denoted by $$r(s,t)= r(K_s, K_t)$$.

We know that for arbitrary $$s, t$$,

$$\displaystyle r(s, t)\leq r(s-1, t)+r(s, t-1).$$

Therefore, $$r(3,n+1) \leq r(3,n) + n$$.

In [1] Erdös said, Faudree, Schelp, Rousseau and I needed recently a lemma stating

$$\displaystyle \frac{r(n+1,n)-r(n,n)}{n} \rightarrow \infty$$

as $$n \rightarrow \infty$$. We could prove this without much difficulty, but we could not prove that $$r(n+1,n)-r(n,n)$$ increases faster than any polynomial in $$n$$. We of course expect

$$\displaystyle \lim_{n \rightarrow \infty} \frac{r(n+1,n)}{r(n,n)} = C^{1/2}$$

where

$$\displaystyle C= \lim_{n \rightarrow \infty} r(n,n)^{1/n} .$$

V. T. Sós and I recently needed the following results ..."

# Conjecture[1]

r(3,n+1)-r(3,n) \rightarrow \infty~, ~~~~~\mbox{for}~~~~ n \rightarrow \infty.

# Conjecture[1]

Prove or disprove that $$r(3,n+1)-r(3,n) = o(n).$$

This conjecture remains unresolved even with the knowledge of Kim's recent results on $$r(3,n)$$: For $$k=3$$, Kim [2] proved a lower bound which matches the previous upper bound for $$r(3,n)$$ (up to a constant factor), so it is now known that

$$\frac{c n^2}{\log n} < r(3,n) < (1+o(1)) \frac{ n^2}{\log n}.$$

Bibliography
1 P. Erdös, Some new problems and results in graph theory and other branches of combinatorial mathematics, Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math., 885, 9-17, Springer, Berlin-New York, 1981.

2 J. H. Kim, The Ramsey number $$R(3,t)$$ has order of magnitude $$t^2/ \log t$$, Random Structures and Algorithms 7 (1995), 173-207.