Simanaitis Says

On cars, old, new and future; science & technology; vintage airplanes, computer flight simulation of them; Sherlockiana; our English language; travel; and other stuff

THE FOUR-COLOR PROBLEM

ARE FOUR colors enough to differentiate adjacent regions on any map? This question, for a long time called the four-color problem, came to mind with the death of mathematician Kenneth I. Appel on April 19, 2013. It was Appel and colleague Wolfgang Haken who established back in 1976 that four colors were indeed sufficient for any possible map. What’s more, their proof depended on a computer—running the equivalent of 50 days straight.

Dr.

Dr. Kenneth I. Appel, 1932-2013, had worked at the Institute for Defense Analyses and taught at the University of Illinois and University of New Hampshire, from which he retired in 2003. Image from the University of New Hampshire.

This was the first time a “computer proof” appeared in mathematics, and not without controversy. Traditionally, mathematical proof consisted of a succession of logical deductions achieved by humans, not performed by exhaustive—and hidden—digital operations. Even today, as quoted in The New York Times (http://goo.gl/55SHz), mathematician Edward Frenkel said, “Like a landmark Supreme Court case, the proof’s legacy is still felt and hotly debated.”

The four-color problem was first proposed by August Möbius (www.wp.me/p2ETap-V3) in 1840. Over the years, it got pecked at, piece by piece. Around 1900 it was proved that any map could be done with five colors; later, that four were enough for any map with less than 38 regions.  Then finally in 1976, Appel, Haken and their computer took care of matters in general.

Regions sharing only a single point, like Colorado and Arizona, aren’t considered here. It’s easy, though, to show that four colors are necessary for non-trivial adjacency.

These

This imaginary geography requires all four colors to separate these regions.

The hard part, Appel and Hazen’s achievement, is showing that four colors are not only necessary, but sufficient as well for any map.

Curiously, it’s easy to show that four colors are not sufficient if a bit of geographical whimsy is allowed. Suppose there’s a natural bridge (see http://goo.gl/Jk1oP) shared by two of the regions. Four colors are no longer enough.

The

The land bridge shared by red and maroon requires this additional color.

An ordinary map is two-dimensional, topologically equivalent to the surface of a sphere. The land bridge raises matters from two dimensions to three, and the regions are now topologically a torus, a doughnut.

The four-color theorem

The four-color theorem doesn’t apply on a doughnut.

And, indeed, it has been proved that seven is the magic number of colors for tori. This proof, paradoxically enough, came prior to the four-color problem’s solution—and without computer help. ds

© Dennis Simanaitis, SimanaitisSays.com, 2013

3 comments on “THE FOUR-COLOR PROBLEM

  1. jeff
    November 4, 2015

    None of these require more than 4 colors. If the two opposite sections were both made blue, the bridges could be red and green. Same for the doughnut.

    • simanaitissays
      November 4, 2015

      Right you are. My examples weren’t complex enough. According to Newman’s “The World of Mathematics,” “On the surface of a torus, whose shape is that of a doughnut or an inflated inner tube, it has been shown that any map may be colored by using seven colors, while maps may be constructed containing seven regions, each of which touches the other six.” That is, the examples need more regions. Hmm…
      A Google search on “Four Color Theorem Torus” reveals an example of a torus (and hence, I’d conjecture, a bridged disc) needing seven. Thanks for your correction.

  2. jeff
    November 4, 2015

    These can both be colored with 4 colors. If the opposite sides are both colored blue, the two bridges can be red and green, with a yellow center. Same for the doughnut.

Leave a Reply to simanaitissays Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Information

This entry was posted on May 1, 2013 by in Sci-Tech and tagged , , .
%d bloggers like this: