Home » Subject » Combinatorics » Ramsey Theory

Diagonal Ramsey numbers

Importance: Outstanding ✭✭✭✭
Author(s): Erdos, Paul
Subject: Combinatorics
» Ramsey Theory
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 Ramsey number.

Conjecture   $ \lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}} $ exists.
Problem   Determine the limit in the above conjecture (assuming it exists).

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

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

[G] W. T. Gowers, Rough structure and classification, GAFA 2000 (Tel Aviv, 1999). Geom. Funct. Anal. 2000, Special Volume, Part I, 79--117. MathSciNet

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

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


* indicates original appearance(s) of problem.
add new comment

diagonal Ramsey numbers

On September 13th, 2010 Anonymous says:

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

reply

Upper bound

On July 9th, 2007 Anonymous says:

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

reply

Comment viewing options

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