# Diagonal Ramsey numbers

 Importance: Outstanding ✭✭✭✭
 Author(s): Erdos, Paul
 Subject: Combinatorics » Ramsey Theory
 Keywords: Ramsey number
 Prize: $100 /$250 (Erdos - Graham)
 Posted by: mdevos on: June 4th, 2007

Let $R(k,k)$ denote the $k^{th}$ diagonal \Def[Ramsey number]{ramsey number}.

\begin{conjecture} $\lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}}$ exists. \end{conjecture}

\begin{problem} Determine the limit in the above conjecture (assuming it exists). \end{problem}

Erdos offered \$100 for a solution to the highlighted conjecture and \$250 for a solution to the associated problem (these prizes are now provided by Graham).

Classic results of Erdos [E] and Erdos-Szekeres [ESz] give bounds on $R(k,k)$ which show that if $\lim_{k \rightarrow \infty} R(k,k)^{\frac{1}{k}}$ exists, then it is in the interval $[\sqrt{2},4]$. Although these arguments are quite basic, little progress has been made in improving these bounds. The best known lower bound on $R(k,k)$ is due to Spencer [S] and the best known upper bound is due to Thomason [T]. They are as follows: $$(1 + o(1)) \frac{ \sqrt 2 }{e} k 2 ^{k/2} < R(k,k) < k^{-1/2 + c / \sqrt{ \log k}} {2k-2 \choose k-1}.$$

Gowers [G] has suggested that resolving these problems might require a rough structure theorem.

## Bibliography

[E] P. Erdos, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. \MRhref{0019911}

[ESz] P. Erdos and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.

[G] W. T. Gowers, \href[Rough structure and classification]{http://www.dpmms.cam.ac.uk/~wtg10/gafavisions.ps}, GAFA 2000 (Tel Aviv, 1999). Geom. Funct. Anal. 2000, Special Volume, Part I, 79--117. \MRhref{1826250}

[S] J. Spencer, Ramsey’s theorem—a new lower bound, J. Comb. Theory Ser. A 18 (1975), 108–115. \MRhref{0366726}

[T] A. Thomason, An upper bound for some Ramsey numbers, J. Graph Theory 12 (1988), 509–517. \MRhref{0968746}

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.

### diagonal Ramsey numbers

Hi, My name is steve waterman.

re - diagonal Ramsey numbers

I have no proof of my conjectured formulas. However, the results are within the limits established in ALL cases. There is also a logic to these numbers as you will see.

http://www.watermanpolyhedron.com/RAMSEY.html

It is my belief that these values are indeed exact...that is, no bounds required, and thus an answer to this riddle - and as I also see it....only to be proven later. It is a big claim no doubt. I doubt that I will ever see a counter-example nor a single proof of say R(5,5) as long as I live. Lastly, knowing that these MAY INDEED BE the correct values...give us a chance to zero in upon these numbers specifically.

steve

### Upper bound

The upper bound has been improved by David Conlon (to appear in Annals)