Diagonal Ramsey numbers

Importance: Outstanding ✭✭✭✭
Author(s): Erdos, Paul
Keywords: Ramsey number
Recomm. for undergrads: no
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.


[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.


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.


Upper bound

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

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.