Lower bound for \(r(k, 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 general \( k\), the best asymptotic bounds for \( r(k,n)\), for \( n\) large, are as follows:

\begin{equation} c \left( \frac{n}{\log n} \right)^{(k+1)/2} < r(k,n) < (1+o(1)) \frac{n^{k-1}}{\log^{k-2} n}. \end{equation}

The upper bound is a recent result of Li and Rousseau [2] who extend Shearer's method to improve the constant factor for the bounds in [1]. The lower bound is given in [3].

Conjecture (1947)

For fixed \(k\), \begin{equation} r(k,n) > \frac{n^{k-1}}{\log^c k} \end{equation} for a suitable constant \(c >0\) and \(n\) large.

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

2 Y. Li and C. C. Rousseau, Bounds for independence numbers and classical Ramsey numbers, preprint.

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