Improved upper and lower bounds on a geometric Ramsey problem

In Graham and Rothschild (1971), Graham and Rothschild consider a geometric Ramsey problem: finding the least N∗ such that if all edges of the complete graph on the points {±1}N∗ are 2-colored, there exist 4 coplanar points such that the 6 edges between them are monochromatic. They give an explicit...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2014-11, Vol.42, p.135-144
Main Authors: Lavrov, Mikhail, Lee, Mitchell, Mackey, John
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In Graham and Rothschild (1971), Graham and Rothschild consider a geometric Ramsey problem: finding the least N∗ such that if all edges of the complete graph on the points {±1}N∗ are 2-colored, there exist 4 coplanar points such that the 6 edges between them are monochromatic. They give an explicit upper bound: N∗≤F(F(F(F(F(F(F(12,3),3),3),3),3),3),3), where F(m,n)=2↑mn, an extremely fast-growing function. We bound N∗ between two instances of a variant of the Hales–Jewett problem, obtaining an upper bound which is less than 2↑↑↑6=F(3,6).
ISSN:0195-6698
1095-9971
DOI:10.1016/j.ejc.2014.06.003