Nate
Four Color Theorem
(See also: The Mathematics Behind the Maps, The Most Colorful
Math of All, and The Story of the Young Map Colorer.)
The Four Color Problem was famous and unsolved for many years.
Has it been solved? What do you think?
The story of the problem
Since the time that mapmakers began making maps that show
distinct regions (such as countries or states), it has been
known among those in that trade, that if you plan well enough,
you will never need more than four colors to color the maps that
you make.
The basic rule for coloring a map is that no two regions that
share a boundary can be the same color. (The map would look
ambiguous from a distance.) It is okay for two regions that only
meet at a single point to be colored the same color, however. If
you look at a some maps or an atlas, you can verify that this is
how all familiar maps are colored.
Mapmakers are not mathematicians, so the assertion that only
four colors would be necessary for all maps gained acceptance in
the map-making community over the years because no one ever
stumbled upon a map that required the use of five colors. When
mathematicians picked up the thread of the conversation, they
began by asking questions like: Are you sure that four colors
are enough? How do you know that no one can draw a map that
requires five colors? What is it about the way that regions are
arranged and touch each other in a map that would make such a
thing true?
When the question came to the European mathematics community at
the end of the 19th century, it was perceived as interesting but
solvable. Prominent and experienced mathematicians who tackled
the problem were surprised by their inability to solve it. Take
for example, this account from The Four Color Problem: Assaults
and Conquesst by Saaty and Kainen:
The great mathematician, Herman Minkowski, once told his
students that the 4-Color Conjecture had not been settled
because only third-rate mathematicians had concerned themselves
with it. "I believe I can prove it," he declared. After a long
period, he admitted, "Heaven is angered by my arrogance; my
proof is also defective." (Saaty & Kainen , 1986,p.8)
A Special Role for the Computer
In 1976, the conjecture was apparently proved by Wolfgang Haken
and Kenneth Appel at the Univeristiy of Illinois with the aid of
a computer. The program that they wrote was thousands of lines
long and took over 1200 hours to run. Since that time, a
collective effort by interested mathematicians has been under
way to check the program. So far the only errors that have been
found are minor and were easily fixed. Many mathematicians
accept the theorem as true.
The proof of the 4-Color-Theorem is a doorway to some
interesting questions about the role of human minds and
computing machines in mathematics. Is it ``fair'' to accept as
true what a computer can verify, even though no single person
can? Does the nature or texture of what humans can discover
about their world change with the use of computers as thinking
tools? Computers are huge and powerful, but finite; will using
them as thinking tools be ultimately limiting? These issues are
raised and considered in Ad Infinitum: The Ghost in Turing's
Machine by Brian Rotman, and Pi in the Sky by John Barrow.
Nate Schmolze
http://www.geocities.com/~nschmolze/
schmolze who-is-at students.wisc.edu
People with great passions, people who accomplish great deeds,
People who possess strong feelings even people with great minds
and a strong personality, rarely come out of good little boys
and girls
L.S. Vygotsky