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]

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

Conjecture[1]

Prove or disprove that \begin{equation} r(3,n+1)-r(3,n) = o(n). \end{equation}

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

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

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.