Conference rusure::math

54.0. "Ramsey Theory" by HARE::STAN () Tue Apr 17 1984 13:06

Ramsey theory began with the following puzzle:

In any collection of six people, either 3 of them mutually know
each other or 3 of them mutually do not know each other.

6 is the smallest number with this property.
This means that the Ramsey number of 3 and 3 is 6, R(3,3)=6.

The Ramsey function is tricky to define rigorously, but I think a
second example should make it clear. R(3,4)=9 means that given
any 9 people, then there is either some 3 of them who are
mutual acquaintances, or some 4 of them that are mutually
unaquainted.  9 is the smallest number with this property.

This can also be described in terms of graphs. Suppose you are
given 14 points and each point is connected to every other point
by an edge that is colored either red or green.
A set of points is called monochromatic if the edges formed by all
pairs of these points are colored the same color.
Then among the 14 points, there must be some 3 points forming a monochromatic
red set or 5 points forming a monochromatic green set.  Since 14
is the smallest number with this property, R(3,5)=14.

Very few exact Ramsey numbers are known.  Here are the results known
in 1980:

R(m,n)=R(n,m)
R(k,2)=k
R(3,3)=6
R(3,4)=9
R(3,5)=14
R(3,6)=18
R(3,7)=23
R(4,4)=18

27 <= R(3,8) <= 30
36 <= R(3,9) <= 37
25 <= R(4,5) <= 28
34 <= R(4,6) <= 44
42 <= R(5,5) <= 55
51 <= R(5,6) <= 94
69 <= R(6,6) <= 102

Now most of the unsolved ones are beyond the reach of exhaustive
search by computer.  However, for some of these, it might be possible
to find counterexamples that would raise the lower bound.
In any case, finding new values for Ramsey numbers would be a
significant mathematical accomplishment.

For those interested in this subject, the standard reference is probably
"Ramsey Theory", by Graham, Rothschild, and Spencer (Wiley 1980).  A
rather difficult book, BTW.
							-- Jerry

I graduated from WASEDA UNIVERSITY two years ago, and then 
working at DIGITAL Japan.

At WASEDA UNIVERSITY I majored in mathematics, especially 
Functional analysis (I prefer Banach space to Hilbert space)
and Graph Theory I studied hard.

So I'm interested in Ramsey numbers. 
I tried to determine R(3,8) but failed !
It is difficult for me to determine R(3,8), R(4,5) and so on.