On cars, old, new and future; science & technology; vintage airplanes, computer flight simulation of them; Sherlockiana; our English language; travel; and other stuff
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.
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.
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.
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.
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