Lower bound for \( r(4, 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)\).

For off-diagonal Ramsey numbers (that is, where \( s\neq t\), the known values are \( r(3,4)= 9\), \( r(3,5)=14\), \( r(3,6)=18\), \( r(3,7)=23\), \( r(3,8)=28\), \( r(3,9)=36\) and \( r(4,5)=25\) while \( 35 \leq r(4,6) \leq 41\) (see the dynamic survey of Radzisowski on small Ramsey numbers in the Electronic Journal of Combinatorics for more bounds and references).

For \( k=3\), Kim [5] recently proved a new 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}

Ajtai, Komlós and Szemerédi [3] earlier gave the upper bound of \( c' \frac{ n^2}{\log n}\) and Shearer [6], [7] replaced \( c'\) by \( 1+o(1)\). It would be of interest to have an asymptotic formula for \( r(3,n)\).

The best known constructive lower bound for \( r(3,n)\) is due to Alon [1]:

\(\displaystyle r(3,n) \geq c n^{3/2}, \)

improving previous bounds of Erdös [4] and others [2].

For \( r(4,n)\), the best lower bound known is \( c (n \log n)^{5/2}\) due to Spencer [8], by using the Lovász local lemma. The best upper bound known is \( c' n^3 / \log ^2 n\), proved by Ajtai, Komlós and Szemerédi [3]. So there is a nontrivial gap still remaining, as repeatedly pointed out in many problems papers [9] of Erdös.

Problem [9]

Prove or disprove that \begin{equation} r(4,n) > \frac{n^3}{\log ^c n} \end{equation} for some \(c\), provided \(n\) is sufficiently large.

Bibliography
1 N. Alon. Explicit Ramsey graphs and orthonormal labelings, Elec. J. Comb. 1 (1994), R12 (8pp)

2 F. R. K. Chung, R. Cleve and P. Dagum. A note on constructive lower bounds for the Ramsey numbers \( R(3,t).\) J. Comb. Theory, Ser. B 57 (1993), 150-155.

3 M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Comb. Theory Ser. A 29 (1980), 354-360.

4 P. Erdös, On the construction of certain graphs, J. Comb. Theory 17 (1966), 149-153.

5 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.

6 J. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), 83-87.

7 J. Shearer, A note on the independence number of triangle-free graphs II, J. Comb. Theory (B) 53 (1991), 300-307.

8 J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math. 20 (1977/78), 69-76.

9 P. Erdös, Problems and results on graphs and hypergraphs: similarities and differences, Mathematics of Ramsey theory, Algorithms Combin., 5, (J. Nešetril and V. Rödl, eds.), 12-28, Springer, Berlin, 1990.