Does the Ramsey limit exist? What is the limit?

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)\). In the special case that \( s=t=n\), we simply write \( r(n)\) for \( r(n,n)\), and we call this the Ramsey number for \( K_n\).

The problem of accurately estimating \( r(n)\) is a notoriously difficult problem in combinatorics. The only known values [1] are \( r(3)=6\) and \( r(4)=18\).

For \( r(5)\), the best bounds [2][3] are \( 43 \leq r(5) \leq 49\). For the general \( r(n)\), the earliest bounds were:

\begin{equation} \frac{1}{e \sqrt 2} n 2^{n/2} < r(n) \leq \binom {2n-2}{n-1}. \end{equation}

The upper bound follows from the fact that the Ramsey number \( r(k,l)\) satisfies

\begin{equation} r(k,l) \leq r(k-1,l)+r(k,l-1) \end{equation}

with strict inequality if both \( r(k-1,l)\) and \( r(k,l-1)\) are even. To see this, if \( n = r(k-1,l)+r(k,l-1)\), for any vertex \( v\), there are either at least \( r(k-1,l)\) red edges or at least \( r(k,l-1)\) blue edges incident to \( v\). Therefore, there is either a red copy of \( K_k\) or a blue copy of \( K_l\). The strict inequality condition is a consequence of the fact that a graph on an odd number of vertices can not have all odd degrees.

The lower bound is established by a counting argument given by Erdős[4], which can be described as follows:

There are \( 2^{\binom{m}{2}}\) ways to color the edges of \( K_m\) in two colors. The number of colorings that contain a monochromatic \( K_n\) is at most

\(\displaystyle \binom{m}{n} 2^{\binom{m}{2}-\binom{n}{2}+1}. \)

Therefore, there exists a coloring containing no monochromatic \( K_k\) if

\(\displaystyle 2^{\binom{m}{2}} > \binom{m}{n} 2^{\binom{m}{2}-\binom{n}{2}+1}. \)

This is true when

\(\displaystyle m \geq \frac 1 {e \sqrt 2} n 2 ^{n/2}. \)

Very little progress has occurred in the intervening sixty years in improving these bounds. The best current bounds are

\begin{equation} (1+o(1)) \frac{ \sqrt 2} {e} n 2^{n/2} < r(n) < n^{-c\log n/\log \log n}\binom {2n-2}{n-1}. \end{equation}

The upper bound is due to Conlon[5] and the lower bound is due to Spencer [6] by using the Lovász local lemma. Using these bounds, we see that \( r(n)^{1/n}\) is between \( \sqrt{2}\) and \( 4\).

Conjecture $100 (1947)

The limit \begin{equation*} \lim_{n \rightarrow \infty} r(n)^{1/n} \end{equation*} exists.

Problem $250 (1947)

Determine the value of \begin{equation*} c:=\lim_{n\rightarrow\infty} r(n)^{1/n} \end{equation*} if it exists.

Bibliography
1 R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1-7.

2 G. Exoo, A lower bound for \( R(5,5)\), J. Graph Theory 13 (1989), 97-98.

3 B. D. McKay and S. P. Radziszowski, Subgraph counting identities and Ramsey numbers, J. Comb. Theory (B), 69 (1997), 193-209.

4 P. Erdös, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294.

5 D. Conlon, A new upper bound for diagonal Ramsey numbers, Anals of Mathematics 170 (2009), 941-960.

6 J. Spencer, Ramsey's theorem--a new lower bound, J. Comb. Theory Ser. A 18 (1975), 108-115.