Graham's Number Problem

[Geoff Exoo]

I want to determine the status of the problem that gave birth
to Graham's number, the oft cited largest number of any use.

The problem is to determine the minimum n such that if the
complete graph on 2^n vertices is edge colored with 2 colors,
and if the vertices are arranged as the vertices of the standard
unit hypercube in R^n, then there will be a monochromatic
K_4 in some plane. Poorly stated, but that's about it.

I have two requests:

1. I'd like to know the original reference(s) for the problem.

2. In the various discussions of the problem available on the
net, it is stated that the lower bound of 6 is widely
believed to be correct. Is 6 still the lower bound?
(If so, it isn't ...)

Thanks for any help,

Geoff Exoo
Dept. Math/CS
Indiana State Univ.
Terre Haute, IN 47809
812-237-2153
g...@ginger.indstate.edu
G-E...@indstate.edu

[tc...@lsa.umich.edu]

In article <a3gdfl$no5$1...@onyx.indstate.edu>,

Geoff Exoo <g...@ginger.indstate.edu> wrote:
>1. I'd like to know the original reference(s) for the problem.

I asked Ron Graham about this once. Apparently his theorem is unpublished.

I don't know when the question first appeared in print. If nobody gives
you a good answer, I would try searching on MathSciNet for "Graham" and
"Euclidean Ramsey" to find survey papers. You might also try asking
Stanislaw Radziszowski; unfortunately, his dynamic survey on small Ramsey
numbers (http://www.combinatorics.org/Surveys/index.html) doesn't seem to
cover Euclidean Ramsey theory.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences