# 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

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

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 $$r(4,n) > \frac{n^3}{\log ^c n}$$ 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.