## TSE@PO.MISSOURI.EDU

#### View:

 Message: [ First | Previous | Next | Last ] By Topic: [ First | Previous | Next | Last ] By Author: [ First | Previous | Next | Last ] Font: Proportional Font
 LISTSERV Archives TSE Home TSE March 2001

Subject:

Re: (VERY) OFF TOPIC - Map coloring

From:

Date:

Tue, 13 Mar 2001 09:05:22 EST

Content-Type:

text/plain

Parts/Attachments:

 text/plain (85 lines)
 ```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 -- ```