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