Posts Tagged ‘inkscape’

Chromatic Number of the Plane Is Still Less Than Or Equal To Seven

May 6th, 2013

Well, it was worth a shot.

Not a breakthrough in the CNP problem

The Chromatic Number of the Plane is defined as the number of colors required to paint the plane such that no two points one unit distance apart are the same color. There are very simple figures that demonstrate a lower bound of 4 and an upper bound of 7 for this number. But this is more or less where knowledge of this problem has stood for the last 50 years. (See the Wikipedia page on this problem for more info.)

I didn’t really expect that I could make a breakthrough, given that real mathematicians have given serious thought to this problem and gotten nowhere, but I thought this would be fun to play with. One potentially useful starting point is to consider how much of the plane one single color could cover. A disk of unit diameter is the biggest blob we can make without two points a unit distance apart. (We’ll allow some fudging about the points on the perimeter of the disk.) We can then pack these disks into a triangular array such that the distance between nearby disks in the array is also one unit. (It’s not clear to me whether we couldn’t get a slightly higher proportion of the plane in one color by flattening the parts of the circles that are closest to other circles. But in any case, the packing with circles should be close to the best we can do.)

It was easy enough to make an array of disks in this fashion using Inkscape. I then copied the array five times, gave each of the six copies its own color, and made them all translucent, so that the overlapping areas could be readily distinguished. The point of this exercise is this: if I could find a way to arrange the six arrays of circles so that they completely covered a region of the plane, I would be able to demonstrate the existence of a coloring that uses only six colors. In other words, I would have decreased the upper bound of the chromatic number of the plane by one, which would have been a significant mathematical result. Note that the circles could and would overlap; any areas of overlap would consist of points that could belong to either color in a valid coloring.

As you can see, I failed. The illustration above was about the best I could do. The white gaps represent areas that could not be colored with any of the six colors. Failing here really proves nothing. Even if I could prove that no coloring using disk arrays like these could work, it wouldn’t prove that there wasn’t some other way to partition the plane that would work better. In fact, Ed Pegg found a configuration where the amount of space needed by the seventh color is very tiny indeed, which gives some hope that 6 colors is possible.

If I could prove that this array of circles really represented the greatest possible proportion of the plane that could be taken up by a single color, (which I can’t) I would in fact be able to improve the lower bound of the CNP. If I didn’t make a mistake, the proportion of the plane taken up by the array of circles works out to π/(8·sqrt(3)), or about .227. Since this is less than ¼, that would mean that the total area that could be taken by 4 colors could not cover the whole plane. Part of the problem here is that even if one could show that the array of circles had the highest proportion of the plane of any “nice” arrangement, it might turn out that an actual coloring of the plane with the fewest colors would end up taking the form of interpenetrating fractal foams, where no individual piece has a measurable area.