The N-Color Theorem?

Date: 07/27/2002 at 07:50:56
From: John Choi
Subject: Eight Color Map Problem???

While thinking about the Four Color Map Problem, I came up with an 
idea: If a polysected plane really does only need four colors to color
it in with no same color touching, then it could be a pattern with 1-D
maps and even 0-D maps! 

So I thought briefly about a 1-D map(obviously a line segment), and
came up with 2 colors for the required number of colors. And when I
looked up 0-D (I guessed a point would be 0-D), I came up with 1
(obviously). 

Ah-ha! I saw a pattern! Maybe the maximum number of colors 
required to fill a polysected n-D space would require 2^n colors?

So that would mean 8 colors maximum would be needed to completely 
fill a multi-divided space with no adjacent sections the same color?
As I thought about this, I became really excited because I thought I 
might have just discovered (well, at least hypothesized) a new and 
important rule. 

Could you please tell me what you think about it? And if you think 
it's wrong, why you think so? Or if anyone else has ever thought this 
before? Or if I'm the first in the world, and it COULD be true, then 
where I should report my amazing discovery? Thanks!

Sincerely and excitedly,

John Choi
Currently Residing in South Korea

Date: 07/30/2002 at 21:02:59
From: Doctor Peterson
Subject: Re: Eight Color Map Problem???

Hi, John.

This is an interesting conjecture, but of course until you have some 
evidence, it's not worth much. And as much fun as it can be to make 
conjectures, it's a lot more fun to find a proof - even if it's a 
proof that your conjecture is wrong.

My first impression when I saw your question was that probably the 
three-dimensional case is not nearly as interesting as you would 
think. Why? First, because if it were interesting I would have heard 
of it; second, because my experience with 2- and 3-dimensional 
problems tells me that when you move up to three dimensions there is 
so much more flexibility that problems like this tend to become 
either impossible or trivial. Notice that in 0 and 1 dimension your 
problem was trivial, but in 2 dimensions it was an extremely hard 
problem. We can expect it to be different again in 3.

So let's try making a dissection of space that requires lots of 
colors, in order to attempt a disproof, or at least learn how 
coloring works in space. A trick I like to use in solving problems is 
to work backward: rather than trying to cut up space, which can be 
hard to visualize, I'd like to build up space out of different-
colored pieces so that each touches all the others and each has to be 
a different color.

I struggled a bit trying to find a good way to make my intuition 
concrete, then realized I should take myself literally and use 
something "flexible": a rope! Suppose I have eight ropes of different 
colors, and just drop them in a tangle on the floor. There's a good 
chance that they will all touch one another, isn't there? Can we 
prove that this is possible? My first thought was to use a 
complicated braid; but then I saw that I can use just the most basic 
idea behind a braid, a crossover. So lay your eight ropes out 
parallel, and then just flip the whole row over itself:

               +   +   +   +   +   +   +   +
              / \ / \ / \ / \ / \ / \ / \ / \
             /   \   \   \   \   \   \   \   \
            /   / \ / \ / \ / \ / \ / \ / \   \
           /   /   \   \   \   \   \   \   \   \
          /   /   / \ / \ / \ / \ / \ / \   \   \
         /   /   /   \   \   \   \   \   \   \   \
        /   /   /   / \ / \ / \ / \ / \   \   \   \
       /   /   /   /   \   \   \   \   \   \   \   \
      /   /   /   /   / \ / \ / \ / \   \   \   \   \
     /   /   /   /   /   \   \   \   \   \   \   \   \
    /   /   /   /   /   / \ / \ / \   \   \   \   \   \
   /   /   /   /   /   /   \   \   \   \   \   \   \   \
  /   /   /   /   /   /   / \ / \   \   \   \   \   \   \
 /   /   /   /   /   /   /   \   \   \   \   \   \   \   \
/   /   /   /   /   /   /   / \   \   \   \   \   \   \   \

Each rope now touches each of the others, so we can't use fewer than 
eight colors.

If you don't think this looks enough like a dissection of space, just 
glue the ropes together where they meet to make sure they stay in 
contact, and let each one puff up to fill as much of space as it can. 
Or, spray foam over the whole thing, making a ninth region that fills 
the rest of space. Now you need nine colors.

And, of course, there was nothing special about the choice of eight 
ropes. We could have used any number; so there is no limit to the 
number of colors you might need.

This is a nice example of the kind of thinking mathematicians do. We 
can visualize an idea in various ways, trying to make our general 
sense of what is happening specific enough that it can be turned into 
a formal proof. I haven't done that last step here, but it's clear it 
can be done.

So your conjecture turns out to be false; but it led to some 
interesting ideas on the way to its disproof, didn't it? Now we know 
why I never heard of anyone writing a thesis on this subject!

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/