A Ramsey Problem on Hypercubes

Consider the vertex set of the unit n-dimensional cube embedded in n-dimensional Euclidean space. Join each pair of vertices by a straight line segment, creating a complete graph. Color the edges of this complete graph in two colors. Graham and Rothschild proved that if n is sufficently large, there is a monochromatic complete graph of order 4 in some plane. They posed the problem of determining how large n must be. Their lower bound was 6 and their upper bound came to be known as Graham's number. Below we give links to colorings that improve the lower bound to 11. In the coloring matrices, we use colors 0 and 1.

 

• n = 3
• n = 4
• n = 5
• n = 6
• n = 7
• n = 8
• n = 9
• n = 10

The following link points to a coloring matrix for n=10 wherein 1/3 of the edges are bicolored. When an edge is bicolored, it can belong to cliques of either color. The matrix is here. Here, we use colors 1 and 2. An entry of 3 indicates a bicolored edge. This topic is discussed in a paper that appeared in the Journal of Discrete and Computational Geometry.

Geoff Exoo

 

Source : 

http://isu.indstate.edu/ge/GEOMETRY/cubes.html