In a message dated 3/13/01 8:09:36 AM EST, [log in to unmask] writes:
> Anyhow, I seem to have a gazillion posts to read through, but none
> from Steve, to which I look forward.
Ken: I do not want to present myself as an expert on the four color map
theorem but I will tell you what I know.
First of all, as I said yesterday, I was taking a class from Ken Appel in
1976 when he became somewhat of a celebrity in the math department at the U
of I by announcing he and a colleague had solved the four color map problem.
The course I was taking was NOT on topology, but Professor Appel took a class
period to explain the algorithms he had used. I had a pretty good memory
then, but after 25 years I don't remember the details of the math, nor did
Professor Appel bring in the actual computer code for us to verify.
The gist of the problem can be easily explained: Draw a square. Then draw
lines from the middle of each side, dividing the square into four parts
(where each "part" is what a map-maker would call a "country"). In this
example , each of the parts is itself a square. How many different colors
would you need to make sure that no two parts ("countries") had the same
color (and thus would run into each other, ruining the map). Obviously four,
right? OK. So let's color the upper right part red, the upper left part blue,
the lower left part green, and the lower right part yellow. So far, so good.
Now start again with an uncolored version of the original square, and
divide it again into four parts like you just did. Only now, draw a small
circle in the middle of the square, making a fifth "country". Each of the
parts look almost the same as before, except the four outer parts are not
squares anymore (they are "squares minus a small arc"), and the fifth part is
a small circle. Now how many colors do you need? Well, one answer is five,
that is, each of the parts from before are the same color (red, blue, green
and yellow), and then we'll color the small circle orange. That works. But
here's another solution. Make the upper left part red, the upper right part
blue, the lower right part red, the lower left part blue, and make the circle
green. That ALSO works, right? We solved it with only THREE colors, even
though we had FIVE "countries" this time instead of FOUR. So the number of
required colors to make a map of all "distinct-color countries" is not the
same as the number of countries, nor is the required number obvious.
What map makers noticed is that no matter how the countries were shaped
(such as the states in the continental US or the countries of Europe), they
could always find a way to show each country in a color that did not run into
another country using only four colors. It sounds impossible, but Tom Gray
posted a URL showing a map of the US drawn this way using four colors (at
http://www.math.gatech.edu/~thomas/FC/fourcolor.html.) . A map maker asked a
mathematician friend if it was true that ANY map drawn in a plane could
ALWAYS be made using only four colors, no matter WHAT the shape of each
individual country was. That's when the "design" problem became a "math"
problem. The problem was abstracted to read something like this:
Take any closed curve in a plane. Divide the closed curve into regions of
any arbitrary shape. Show that only four colors are needed to color in each
region such that no two adjacent regions have the same color.
Now it's not a "map design" problem. It's a topology (i.e., math) problem.
The mathematicians approached the problem by considering how a closed
curve could be subdivided into regions. They realized that certain patterns
emerged (such as "the next subdivision creates one extra region that shares a
common boarder with at most four other regions", "the next subdivision
creates one extra region that shares a common boarder with at most one other
region", etc). They reduced each of these cases to graphs connected by nodes.
They showed that every single case was just a variation of a certain set of
interconnected nodes. In 1976 it was believed that there were 1476 different
patterns, and recently it has been shown that many of those cases can be
recast into other cases, so that there are actually under 700 unique possible
patterns.
Each of the interconnected node patterns leads to complex graphs that must
be separately considered. That's where the computer comes in. Appel
programmed the computer to "color in" each of the cases of possible graphs.
To give you an idea as to the complexity of the calculations, it took him
1200 hours of computer time to compute the answer for each of the 1476 cases
he had found, about an hour of computer time per case. In 1976, even a
microprocessor was running at over 2,000,000 instructions per second. So
assuming they used nothing more than a lowly microprocessor, it took (at
least) 7,200,000,000 operations to verify each of the 1476 node cases, for a
total of (at least) 10,627,200,000,000 operations to check everything. That's
a gazillion operations.
If you want more details, Tom Gray's cited paper looks pretty good.
-- Steve --
