Wednesday, July 08, 2009

Why your coloring book can outsmart mathematicians

Here's an interesting question. Let's say I give you a political map of the world and tell you to color it in so that no bordering countries are the same color. How many different crayons would you need? Six? Seven? What if I gave you a map that had not only country boundaries, but also county lines? You'd probably ask for a few more crayons. How many colors would you need now? Ten? A dozen?

Turns out that I could selfishly hoard away the big box of Crayolas and, like a kid-friendly Olive Garden restaurant, ask you to be satisfied with four measly crayons. You'd still be able to accomplish the task with ease, though it might take you a while. In fact, I couldn't draw you a map that would require more than four colors to fill.

I'd prove it to you, but I'm a little daunted by the fact that mathematicians banged their heads against the Four Color Theorem for 125 years or so before getting it to budge an inch. It all started in 1852, when a young, unsuspecting botanist named Francis Guthrie was coloring in the counties on a map of England. Pretty much the most innocent hobby you could imagine, right?

Wrong. As Guthrie studiously filled in the map, he noticed that he never seemed to need a fifth color. In fact, he began to suspect that this might be true of all maps, so he decided to write to his younger brother, a student of Augustus De Morgan, and so unleashed the problem that was to confound mathematicians for more than a century.

What I love about this problem is that it's astoundingly easy to get your mind around, but extraordinarily difficult to prove. The proof has a long and bloody history; the century after Guthrie's observation was marked by hopeful theories that were each dashed to the rocks as insufficient. It wasn't until the advent of computer science that mathematicians made any headway.

In 1976, a pair of University of Illinois mathematicians named Kenneth Appel and Wolfgang Haken, with extensive assistance from a computer, proved that a map requiring 5 colors didn't exist. (Now Haken happily boggles young minds by presenting the problem to local high school students, the university reports.)But even after the media whirlwind surrounding their proof subsiding, doubts crept into the mind of other mathematicians on its solidity. Though they were able to bolster chinks pointed out by critics, many mathematicians remained unsatisfied. Maybe it just seemed wrong that a theory you could demonstrate with a few crayons and a three-year-old needed so much technology to prove:

Part of the Appel-Haken proof uses a computer, and cannot be verified by hand, and even the part that is supposedly hand-checkable is extraordinarily complicated and tedious, and as far as we know, no one has verified it in its entirety. We have in fact tried to verify the Appel-Haken proof, but soon gave up. Checking the computer part would not only require a lot of programming, but also inputing the descriptions of 1476 graphs, and that was not even the most controversial part of the proof.

That's from Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas, the team that greatly simplified the proof in 1995. While it's much easier to verify than Appel-Haken, you still can't check it by hand. The authors admit, "However, an argument can be made that our `proof' is not a proof in the traditional sense, because it contains steps that can never be verified by humans." Georges Gonthier streamlined it again in 2005, but you still need computer software. But interestingly enough, figuring out how to color maps could solve problems Guthrie never predicted, like how to provide cell-phone service with the minimum number of channels.

Maybe you're not convinced? Be an iconoclast! Play around with the problem and see if you can draw a map that requires five colors. (Warning: link is an excellent procrastination tool.)

1 comment:

  1. Best treatment of the map coloring problem I have ever read!