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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.