# 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:

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

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

$$r(k,l) \leq r(k-1,l)+r(k,l-1)$$

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

$$(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}.$$

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.