Bounds for growth of \(r(3, n)\)
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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\),
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
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,
917, Springer, BerlinNew 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), 173207.
