Four color map theory

[Beruang]

Forgive me if this has been covered before, but I couldn't find it in the archives.

Any high-school geometry student can demonstrate the truth of the four-color map theory thusly:

* On a flat map, any region must have either an odd or even number of neighbors.

* If a region has an even number of neighbors, only three colors are needed -- one for the "central" region, and two more to be used alternately in the neighbors.

* If there are an odd number of neighbors, then a fourth color is needed for the "last" neighbor.

However, I've been told that a "demonstration" isn't the same as a "proof." I don't debate that -- what I want to know is why is the demonstration above not considered a proof?

Not being a mathematician, I await enlightenment...

[Wendell Wagner]

Beruang writes:

> On a flat map, any region must have either
> an odd or even number of neighbors.

O.K., the problem with your "proof" is that you start by saying that any one region must have either an even or a odd number of neighbors. True, but then you go on to assume that every region on the map has either only even or only odd numbers of neighbors. You're restricting the cases you consider already. Some maps have both regions with an even number of neighbors and regions with an odd number of neighbors.

[Earl Snake-Hips Tucker]

In his book "Time Travel and Other Mathematical Bewilderments," (Chapter 10, "Six Sensational Discoveries") Martin Gardner shows exactly how the four-color theory was disproved.

My paraphrase:

H. S. M. Coxeter a geometer at the University of Toronto had suspected that this conjecture was false.

He was vindicated in November 1974 when William McGregor, a graph theorist of Wappingers Falls, NY, constructed a region of 110 regions that cannot be colored with fewer than five colors.

McGregor's technical report appeared in 1978 in the "Journal of Combinatorial Theory," Series B.

How 'bout dat?

(And don't try to contradict this unless you've read the book.) ;)

[Beruang]

Forgive me if I'm being dense, but I don't follow you. Yes, every region on the map would have either an odd or even number of neighbors. No matter which region you choose to start coloring in, you will need either three colors (even number of neighbors) or four colors (odd number of neighbors). Each of its neighbors would have either an odd or even number of neighbors, and the same rule applies. Each of *those* neighbors would have... and so on.
I don't see how a map in which some regions have an odd number of neighbors and other regions have an even number of neighbors forms an exception.

I have just realized that it *is* possible that a region with an even number of neighbors may require four colors, *if* you started coloring in an adjacent region with an odd number of neighbors. But if you start coloring in elsewhere, the problem disappears.

Perhaps this is where the "proof" breaks down?

[Beruang]

Mjollnir --

Alright, I will look for the book. But I clearly remember somebody using a computer program to prove that four colors *were* the maximum necessary. I think that came along in the early '80s, and was even the subject of a US stamp. so it *must* be true! ;)

Being utterly unqualified to judge between two competing mathematicians, I now tip-toe swiftly away..

[David B]

Here ya go, guys: http://www.straightdope.com/classics/a1_126b.html

One of the profs who worked on this, Wolfgang Haken, was my calc professor in college. He never could explain calculus worth a darn, so I'm glad to know he apparently had talents elsewhere.

[glee]

Mjollnir,

I haven't read that particular book by Martin Gardner, but I assume it's a pun.
Isn't it?

[Earl Snake-Hips Tucker]

Well, let's just put it this way--this chapter is essentially a reprint of his article that ran in the April 1975 "Scientific American" magazine.

[Squid Vicious]

David,

You're right, Haken couldn't explain calculus worth a damn. Of course it might have something to do with english being a second language to him. Aside from the four color map thing, the thing I remember most about him was that he wore the same ugly sweater every day, and he smelled really bad. In fact, the entire math department was so full of europeans with only a passing aquaintence with soap that we began calling the aroma permeating Altgeld Hall as the stench of math.

[David B]

Squid said:You're right, Haken couldn't explain calculus worth a damn. Of course it might have something to do with english being a second language to him.I dunno. I never had a problem understanding his words -- just understanding the overall way he taught calculus. Several of us from class, being the budding scientists we were, did an experiment one time. Half of us paid no attention in class (or didn't go) and read the related info from the book. The rest of us paid attention in class and tried to understand it, then went to the book. In both cases (the groups switched halfway through our experiment), those who listened to him before reading the book actually had more trouble understanding the material than those who just read the book!Aside from the four color map thing, the thing I remember most about him was that he wore the same ugly sweater every day, and he smelled really bad.I don't remember the sweater, though I vaguely recall the smell. What I remember about the way he dressed was that his pants were always about 3 inches too short.

So when did you have him as a professor?

[Greg Charles]

Here's a counter example to your proof. The central country is bordered by an even number of countries, but two of the bordering countries that would be colored the same by your method actually border each other. Weird shapes are allowed by the problem, as long as the countries are contiguous. (That is, something like Michigan would violate the problem.)

I'm not sure what the applications of proving flat maps need only four colors is, but the general map coloring problem has many applications. The problem is to color a random map, flat or otherwise, with the minimum number of colors. This problem is in a class called NP complete. Basically that means that the fastest known way to solve them is to try every possible combination to see which is best, and yet there is no proof that this is the fastest possible method to solve them. There are many NP complete problems that look very different, but (and this is the fascinating part) if a faster method could be found to solve any one of them, then all of them could be solved by that same method. Now, such a method probably doesn't exist since brilliant people have been searching for it for some time, but who knows? Finding it would be a huge boon to humanity.

Other NP complete problems:

Travelling salesman: Salesman wants to visit a given set of cities and return home. What's the shortest possible route?

Knapsack: a burglar can only fit so much stuff in his bag. What objects should he take?

Longest path: a project has certain identified tasks. Some are dependent on others, while some can be run in parallel. What's the shortest time of completion for the project?

[Beruang]

But what if you started with Michigan?

[Greg Charles]

It doesn't matter about starting with Michigan. My point with Michigan is that it violates the map coloring problem entirely, while strangely shaped states/countries are allowable. It would be easy to come up with a flat map that required more than four colors if you allowed states/countries to be non-contiguous. I was just using Michigan as an example.

[Boris B]

It would be easy to come up with a flat map that required more than four colors if you allowed states/countries to be non-contiguous.

Whoa whoa. I'm really surprised. States and countries can be non-contiguous, but maps can still be colored with four colors (I'm thinking of Indonesia, Malaysia, etc.) Or so I thought. What's an example of regions in two-dimensional space that can't be colored in four colors with nobody sharing a border with a same-color region? I'm not assuming that it would be easy to describe, it's just that I can't even imagine it.

My "proof" (conceding in advance that it might not really be a proof) for the four color problem is to start out with a giant donut with a three-slice pie in the middle. That is, three mutually touching regions surrounded by a single circular region - each with a separate color. Now, no conceivable manipulation can require a fifth color.

It seems like (and I could be wrong) that there are a limited number of "geometrically significant" transformations you can do. Obviously, modifying the size of any region doesn't really matter. What matters is ways of dividing the regions - each region can be divided or joined at will, but one of the four colors should do the job.
If you want, you can cut the outer donut into many regions, but no chunk of the donut can touch more than one of the inner pie regions, if any other chunk of the donut touches three.
If any chunk of the donut touches two of the pie slices, no other chunk of the donut can touch more than two.
If you want to cut the outer donut with a slice parrallel to the outer edge of the donut, say creating two concentric donuts or donut sections, that's fine too, but not all of your skinny baby donuts can touch the pie in the middle.

But I won't be surprised if this doesn't constitute proof, since the standards of proof with this kind of thang seem pretty astronomical.

------------------
- Boris B, Hellacious Ornithologist

[Boris B]

Non-fatal error:
You actually can have a big chunk of the outer donut touching three pie slices, and have another donut chunk touching two pie slices. But the chunk touching two can still be the same color as the pie slice it isn't touching.

[Mr. Sheepshead]

I'd really like to see Mr. McGregor's 110 region map, is it available on-line anywhere? Or is there anything similar I can look at on-line?

[RM Mentock]

Mr. McGregor was an April Fool joke.

Boris B:Whoa whoa. I'm really surprised. States and countries can be non-contiguous, but maps can still be colored with four colors (I'm thinking of Indonesia, Malaysia, etc.) Or so I thought. What's an example of regions in two-dimensional space that can't be colored in four colors with nobody sharing a border with a same-color region? I'm not assuming that it would be easy to describe, it's just that I can't even imagine it.

Easy. Five countries on ten islands, each island is owned by two countries, each country is on four islands, such that every country touches all the other--so you need five colors.

Part of your fatal error in your proof is the same as Beruang's, you didn't *use* the flatness condition in your proof. Since you didn't, your proof should also work for the torus, but it obviously doesn't. It is easy to draw seven (contiguous) countries on a torus so that they all touch each other. And it was proven long ago that seven was enough, for a torus.

.

[bizerta]

One should disregard the "proof" shown in the April, 1975, issue of Scientific American. IIRC, the Mathematical Games column in that issue listed several, recent mathematical breakthroughs. They were all hoaxes. It was, after all, the April issue.

[jcgmoi]

Beruang: Your demonstration fails as a proof because it addresses only local elements of a global scheme. Say you color region A as you suggest. Consider region B, which is contiguous to some regions(s) contiguous to region A. You don't have the freedom to color B as you did A since some color(s) have already been determined. Any proof must show that those colors 'forced' on region B can be accomodated in a 4-color scheme, and that's where your demonstration falls short.

[Omniscient]

RM you need six colors for your example, don't leave out the water, it counts as a region on the map.

Let me throw my hat into the ring maligning the teaching abilities of Dr. Haken. He really sucked, and he wasn't the most forgiving or willing to put in time away from class. The soap issue didn't really inspire many to seek out of class help either, a theme in the math depertment. What fun!

[Ringo]

I don't know how the super computer jocks did it, but a few minutes of screwing around in Corel Draw produced a seven region map that requires five colors. Region 1 is central and is bordered by Regions 2, 3, 4, 5, 6 & 7. Region 2 is bordered by 1, 3 & 6. R3 is bordered by 1, 2, 4 & 6. R4 is bordered by 1, 3, 5 & 6. R5 is bordered by 1, 4, 6 & 7. R6 is bordered by 1, 2, 3, 4, 5 & 7. R7 is bordered by 1, 5, 6 & 7.

I can't put it up anywhere on the Web, but I'll be glad to e-mail anyone a bitmap.

[Boris B]

Uhh, Beatle? I thought the supercomputer jocks proved that what you have done in CorelDraw couldn't be done (assuming the contiguous-regions-only and flat-space caveats above). So either you're pulling our legs or the supercomputer jocks were wrong. Or else I'm very confused.

Nahh, couldn't be. I'm NEVER confused.

[Ringo]

I'm often more of an empiricist than a theoretician.

[Boris B]

Okay, I sketched out the above example, and assigned four colors to the regions:
Region 1 is blue
Regions 2, 4 and 7 are yellow
Regions 3 and 5 are orange
Region 6 is red.

I feel much better now.

[Ringo]

Yeah, that works with four. Ah, well...nice thing about the empirical approach is that you aren't often dismayed by early failures. Maybe it will take 110 regions. I'll continue to hack at it.

[C K Dexter Haven]

The difference between a proof and a demonstration:

There is nothing in your demonstration that relies on the surface being flat. You could still make your odd-even argument (which is true LOCALLY). However, it is pretty easy on the surface of a torus (donut shape) to draw a map that requires more than four colours.

[jens]

Aside from shape of surface (the assumption is a plane), the problem with this "proof" or demonstration is that it only addresses a central region surrounded by border regions without considering that those border regions might have neighbors OTHER than the central region with colors of their own to worry about. In other words, this demonstration only addresses maps with a hub and spoke shape.

[Beruang]

CKDext --

I don't understand -- one of my conditions was a flat surface.

jens --

Maybe this is my failing, but I see the principle applying to any region anywhere on the map. Perhaps my error is in viewing *every* region as a hub.

Now, it is not too difficult to draw a "hub-and-spoke" arrangement that works just fine, and then draw additional regions in the third and fourth tiers that would require five colors. But you can re-assign colors to the same map, and it works just fine.

Maybe that's it? The fact that this approach doesn't work for *every* region you choose to start with, invalidates it as a general proof?

[John W. Kennedy]

Longest path: a project has certain identified tasks. Some are dependent on others, while some can be run in parallel. What's the shortest time of completion for the project?

That sounds simpler than NP-complete, unless there is an additional restriction on maximum number of parallel tasks.

------------------
John W. Kennedy
"Compact is becoming contract; man only earns and pays."
-- Charles Williams

[JonF]

---------------
Knapsack: a burglar can only fit so much stuff in his bag. What objects should he take?
-----------------

Side note: although the generalized Knapsack problem is NP-complete, there has been some progress in solutions. Trapdoor ciphers based on the Knapsack problem have been broken as long ago as 1984. See Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's signature scheme (http://www.research.att.com/~amo/doc/arch/knapsack.attacks.pdf), The rise and fall of knapsack cryptosystems (http://www.research.att.com/~amo/doc/arch/knapsack.survey.pdf), Practical Attack against Knapsack based Hash Functions (http://www.dmi.ens.fr/~granboul/recherche/data/hash.ps.gz), [url=http://www.mi.informatik.uni-frankfurt.de/research/papers/ritter.knapsack_cryptosystems.1996.psBreaking Knapsack Cryptosystems by Max-Norm Enumeration[/url].

This is my first attempt at UBB code, hope I don't screw up ...

------------------
jrf

[JonF]

Rats.


------------------
jrf

[knappy]

I have 2 bitmaps from a 'Macalaster College Problem of the Week', which was a slightly modified version of Martin Gardner's 4/75 April Fools column. The author of the Problem of the Week was Stan Wagon, archived by J. Erickson, but unfortunately I can no longer access this site & my search engine can't find it.

One of the bitmaps is 4-colored, the other blank. E-mail me if you want one or both.

Wagon gave a hint on solving this, based on Kempe chains (named after an early 'prover' of the theorem). Say the colors are red, yellow, blue & green, and you've partially 4-colored the map. Pair the colors, thinking of red/yellow islands within blue/green seas (with lakes possible, and islands within lakes, etc.) You have red/yellow and blue/green Kempe chains.

If you run into a jam, you can reverse the coloring within a Kempe chain touching the problem spot (i.e., red becomes yellow & vice versa). Proving that this always works is extremely hard, but in practice, it's pretty easy.

JonF, thanks for the knapsack links. I'll be sure to check them out.

[Greg Charles]

I think JWK is right. The longest path problem assumes that you have a fixed number of resources to throw at the tasks.

The "attack" on the knapsack problem is interesting. I wonder if it could be used to "attack" the other NP complete problems as well? If I remember right, the heuristic partial solutions weren't universal, the way a true solution would be.