View Full Version : Four Color Theorem

Matthew

2005-Sep-06, 07:26 AM

So you only need four color's to color a map? What if all the localaties met at a single point? See the attached diagram. Lets a ssume the lines are perfect and borders intersect at a single point. Would that mean that more than 4 colors are needed?

01101001

2005-Sep-06, 08:05 AM

Wikipedia: Four color theorem (http://en.wikipedia.org/wiki/Four_color_theorem)

The four color theorem states that any plane separated into regions, such as a political map of the counties of a state, can be colored using no more than four colors in such a way that no two adjacent regions receive the same color. Two regions are called adjacent if they share a border segment, not just a point.

jfribrg

2005-Sep-06, 12:50 PM

There is a book, called Four Colours Suffice (http://www.amazon.com/exec/obidos/tg/detail/-/014100908X/qid=1126010749/sr=8-1/ref=sr_8_xs_ap_i1_xgl14/102-9099553-7088128?v=glance&s=books&n=507846) that gives the history of the problem. It is a layman's book, but the math level varies. Sometimes it is too simplistic. Other times it goes too fast, but in all, I have a better understanding of the proof than I did before I read it.

worzel

2005-Sep-06, 01:55 PM

But have they proved it for all colours?

jfribrg

2005-Sep-06, 02:13 PM

But have they proved it for all colours?

I'm not sure I understand what you mean. It is trivial to prove that 3 or fewer colors is not sufficient. All you need is to show that there is a map where 3 colors aren't enough. Here is a simple counterexample: Start with a thick circle with a hole in the center. Section the circle into 3 parts, each of which must be a different color. The hole in the center must also be different from the first 3 colors used on the circle, which proves that 3 colors are too few. For 5 colors, take a 4 color map and arbitrarily change one of the areas to a color that isn't anywhere else on the map. For 6 colors, take the above mentioned 5 color map and change one area to a color that isn't yet used. Do this for as many colors as you have in your crayon box.

hhEb09'1

2005-Sep-06, 02:39 PM

I know what he means. **bap** now, say you're sorry

It has long been known that a map on a torus requires seven colors, and seven always suffices. To see that seven is necessary, take a torus, and divide it into bands of seven different regions encircling the torus through its hole. Now, cut a line around the top of the "donut" and slide the outside parts along the line 2 1/2 regions. All seven regions will share a boundary with all six other regions.

worzel

2005-Sep-06, 03:23 PM

What I acutally meant was although it is true for the traditional colours used on a political map, has it also been proven for, say, 4 slightly different shades of pink.

I know what he means. **bap** now, say you're sorrySorry. :o

zrice03

2005-Sep-06, 09:27 PM

It doesn't matter which colors you use, as long as they are all different. So, yes, it would work for 4 different shades of pink because they are all different. It would also work for four shades of blue, green, maybe two of red and two of grey, etc.

Basically, when you have four countries that all touch each other, one of those contries has to be completely surrounded. Notice in jfribrg's diagram, the brown country is completely surrounded. Go ahead and try it yourself on a piece of paper.

There is, however, an unstated premise: All the countries have to be in one piece. For example, the United States is not in one piece because of Alaska. There are two large "pieces" of the U.S. (and various islands)... If you tried this on the actual map of the Earth, you might not find the 4 color theorem is true (then again, it might be. I've never tried it).

worzel

2005-Sep-06, 11:33 PM

It doesn't matter which colors you use, as long as they are all different. So, yes, it would work for 4 different shades of pink because they are all different. It would also work for four shades of blue, green, maybe two of red and two of grey, etc.

Ok, thanks for the clarification ;)

There is, however, an unstated premise: All the countries have to be in one piece. For example, the United States is not in one piece because of Alaska. There are two large "pieces" of the U.S. (and various islands)... If you tried this on the actual map of the Earth, you might not find the 4 color theorem is true (then again, it might be. I've never tried it).

I think you would find that the 4 color theorem is true irrespective of the potential problem you raise, it just isn't the same thing you're describing.

hhEb09'1

2005-Sep-07, 09:08 AM

LOL. Yep. Just take any map of any set of N countries and put an "embassy" for each one, in each one. Then, you need N colors.

zrice03

2005-Sep-08, 05:20 AM

LOL. Yep. Just take any map of any set of N countries and put an "embassy" for each one, in each one. Then, you need N colors.

Exactly.

jfribrg

2005-Sep-08, 06:56 PM

Basically, when you have four countries that all touch each other, one of those contries has to be completely surrounded.

Basically that is the key, but proving it is the problem.

There is, however, an unstated premise: All the countries have to be in one piece.

Actually, this is stated explicitly in the formal definition of the problem.

For example, the United States is not in one piece because of Alaska.

Hawaii also, but the problem is limited to contiguous areas on a flat (two dimensional) surface that share a border. IIRC, for these purposes, Michigan is a problem too.

worzel

2005-Sep-08, 10:06 PM

There is, however, an unstated premise: All the countries have to be in one piece.Actually, this is stated explicitly in the formal definition of the problem.

Exactly. ;)

peter eldergill

2005-Sep-08, 11:01 PM

Are there any practical applications for the four colour theorem or is it just one of those "neat things" to know like Fermat's Last Theorem and Relativity (Ha! Kidding!)

Pete

worzel

2005-Sep-08, 11:05 PM

Are there any practical applications for the four colour theorem or is it just one of those "neat things" to know like Fermat's Last Theorem and Relativity (Ha! Kidding!)

Pete

Maybe it's why there are CMYK printers - but that would suggest that there is a three colour theorem waiting to be proved.

Halcyon Dayz

2005-Sep-08, 11:15 PM

It is obviously useful for (game)mapmakers.

BenM

2005-Sep-08, 11:16 PM

I spent an entire summer as a kid trying to draw maps that would disprove the theorem. It wasn't a complete waste of time, because it did get me started down the path of scientific inquiry.

worzel

2005-Sep-09, 12:25 AM

I was so naive when I first saw the problem that I figured that as it was obvious, I would be able to come up with a simple proof and dazzle the world :o

peter eldergill

2005-Sep-09, 03:44 AM

My Uncle thought he had a proof of Fermat's Last theorem, less than a page. Even I found his mistake quickly.

He also had a "proof" that an angle can be trisected. I couldn't follow what he was doing, as it was purely geometrical, which I'm not familiar with

Well, gotta go!

Pete

montebianco

2005-Sep-09, 04:03 AM

IIRC, for these purposes, Michigan is a problem too.

I guess the problem would be not that Michigan comes in two pieces (they're easy enough to connect, at least on the map), but that neither Michigan and Illinois nor Indiana and Wisconsin share a border...

montebianco

2005-Sep-09, 04:05 AM

My Uncle thought he had a proof of Fermat's Last theorem, less than a page.

Maybe it was the same proof Fermat had :)

Enzp

2005-Sep-09, 04:16 AM

And we try to keep as much water as possible between us and Canada. (Here being Michigan) If the water is blue, does that count as a color?

I'm with Worzel here.

And what if the colors run?

Who among us before they were old enough to know how smart they weren't didn't figure, "Oh, I can beat that, lemme at it..."?

montebianco

2005-Sep-09, 05:12 AM

And we try to keep as much water as possible between us and Canada. (Here being Michigan)

Was just there a couple of weeks ago, didn't look like a particularly long bridge :)

hhEb09'1

2005-Sep-09, 10:03 AM

He also had a "proof" that an angle can be trisected. I couldn't follow what he was doing, as it was purely geometrical, which I'm not familiar withHere's a way (http://mentock.home.mindspring.com/trisect.htm) to trisect an angle. :)

jfribrg

2005-Sep-09, 10:54 AM

Here's a way (http://mentock.home.mindspring.com/trisect.htm) to trisect an angle. :)

From page 101 of the book "Elements of Abstract Algebra", which provides an interesting use of field theory to provide straightedge-and-compass proofs, this trisection is addressed.

First let us show how angles may be trisected easily if we allow and incorrect usage of the straightedge. (Apparently this practical construction was known to ancient geometers.)

As with other math problems, the "rules" are clearly defined. From the same book, here are the rules:

(1)the points (0,0) and (1,0) are constructible. Any two points of the plane may be chosen for (0,0) and (1,0) and the distance between them taken as the unit length.

(2) A circle with a constructible point as center and a constructible length as radius is constructible. A constructible length is the distance between two constructible points.

(3) The intersection of two constructible lines is a constructible point.

(4) The points (or point) of intersection of a constructible line and a constructible circle are constructible

(5) The points (or point) of intersection of two constructible circles are constructible

Step 3 in the link from the previous post is the illegal operation. The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.

The book then provides a single counterexample. First, the constructible points and operations are restated in terms of complex numbers, and a proof is given that these operations and points form a field. It then shows using field theory that it is impossible to trisect a 60 degree angle.

worzel

2005-Sep-09, 11:06 AM

Step 3 in the link from the previous post is the illegal operation. The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.

You could use the compass to measure the chord and then mark that off from E or F.

hhEb09'1

2005-Sep-09, 01:56 PM

Step 3 in the link from the previous post is the illegal operation.Step 2 is also "illegal". :)

However, I use the straightedge legally, throughout.

The result is also that you get an angle that is 1/3 of the original, but the angles are in different places. When you bisect an angle using "legal" operations, you split the original angle in half, but here you generate an angle elsewhere, which is a different issue.No, it's not. As worzel points out, you can use that angle to easily construct a copy anywhere else, including between the original angle.

Enzp

2005-Sep-10, 03:53 AM

Montebianco - which bridge? Try walking that Mackinac bridge, she is longer than she looks. Every so often a car or truck blows over on it. We have our ways...

worzel

2005-Sep-10, 11:03 AM

Two questions.

The first to jfribrg or anyone else who knows the answer. What purpose are those 5 rules of geometric construction supposed to serve given that they appear not to define what can actually be done, geometrically, with a straight edge and compass?

The second to hhEb09'1. Did you come up with that trisection yourself?

hhEb09'1

2005-Sep-10, 02:34 PM

The second to hhEb09'1. Did you come up with that trisection yourself?The neusis or verging "cheat" trisections have been known for over two thousand years. That particular one is my modification of Archimedes's--which, according to The Book of Numbers by Conway and Guy, uses a marked ruler--which is an incorrect use of a ruler, as jfribrg's link says. Apparently, a lot of people know about the incorrect use of rulers, so I changed it to an incorrect use of a compass instead. :)

montebianco

2005-Sep-11, 01:34 AM

Montebianco - which bridge? Try walking that Mackinac bridge, she is longer than she looks. Every so often a car or truck blows over on it. We have our ways...

I was talking about the one between Detroit and Windsor, where one can drive in a southward direction from the US into Canada :)

peter eldergill

2005-Sep-11, 04:30 AM

Wow, guys & gals, I didn't mean to start a conspiracy (ahem) about trisecting an angle. There seems to be some gaps in the general idea. Specifically, I don't actually know what the original theorem says (trisecting angles) and why there is a "fake" proof

Could someone please state for me exactly what the theorem is, and thy there is a "fake" proof for it? (As far as I know, you can't trisect an angle with a stright edge and compass) Is there an exception maybe for a specific case?

L8R

Pete

hhEb09'1

2005-Sep-11, 04:43 PM

Could someone please state for me exactly what the theorem is, and thy there is a "fake" proof for it? (As far as I know, you can't trisect an angle with a stright edge and compass) The construction I linked to is an actual trisection, but the classical construction uses a rule with no marks, and a compass that collapses as soon as you lift it up from drawing a circle--so that construction is illegal according to those criteria. And so is worzel's idea of transferring a chord length and marking it off from another point--but there are alternate ways of achieving the same thing.

Enzp

2005-Sep-13, 06:04 AM

Ah, the Ambassador Bridge. Longest suspension bridge in the world...in 1929. 1850 foot span and 7490 feet long. And a lovely bridge.

The Big Mac has an 8614 foot span and is five miles long.

Maddad

2005-Sep-14, 04:42 PM

Basically that [when you have four countries that all touch each other, one of those contries has to be completely surrounded.] is the key, but proving it is the problem.I proved it 34 years ago in high school with pencil and paper before anyone had computers. I've since given talks on why the current attempts to solve the problem are not trying to solve the problem, but rather trying to rename it. I've also taken the obligatory cheap shots at computers used in a supposed proof. An image of the proof is the only tatoo that I've ever considered getter, but I chickened out.

I spent an entire summer as a kid trying to draw maps that would disprove the theorem. It wasn't a complete waste of time, because it did get me started down the path of scientific inquiry.Yep. That how I started too.

David Madison

Maddad@Hotmail.com?Subject=FourColorMapTheorem

worzel

2005-Sep-14, 05:17 PM

I proved it 34 years ago in high school with pencil and paper before anyone had computers.Wow! I don't suppose you've got your proof on the web somewhere, have you?

Maddad

2005-Sep-14, 06:56 PM

No sir, not on the web. I've been thinking of trying to find someone to officially recognize a solution. I remember talking to a guy in the science department (head?) at Ohio State University several years ago. He said, "Yeah, sure, send in your proof so that I can disprove it" or something like that. He also was worried that I'd submit reams of computer data, and he didn't want to have to read through it all. He considered himself a lightning rod for people working on the puzzle.

It's not really hard at all. I should have spoken with him again, but I was a bit frosted by his demeanor, and just never got around to it. Think I'll write it up tonight and put it on my website. My temporary website ( http://www.geocities.com/davidmadison01 ); my regular one ( http://www.maddad.org ) is down.

worzel

2005-Sep-14, 09:10 PM

Has anyone checked it over for you? (not that I'm offering, not much of theorem cruncher me)

hhEb09'1

2005-Sep-15, 04:37 PM

I proved it 34 years ago in high school with pencil and paper before anyone had computers. I've since given talks on why the current attempts to solve the problem are not trying to solve the problem, but rather trying to rename it. I've also taken the obligatory cheap shots at computers used in a supposed proof. An image of the proof is the only tatoo that I've ever considered getter, but I chickened out.Post it! if we can't find the error within a day, I'll eat my hat. :)

Maddad

2005-Sep-15, 11:51 PM

Wow! I don't suppose you've got your proof on the web somewhere, have you?I just asked Phil in an email if he would support my authorship if I posted the solution here. If he agrees, I'll step you through it.

peter eldergill

2005-Sep-16, 01:42 AM

Maddad said:

I proved it 34 years ago in high school with pencil and paper before anyone had computers.

Are you referring to the four colour theorem in total, or just a part of it. It would be a remarkable achievement to do something like that in high school, although I am a bit skeptical that you have a valid proof....

As far as I know, the computer proof of this takes into consideration all 2000 (or so) possible cases that arise from the theorem. I'm curious to see how you could reduce that into something simple

Looking forward to it! I'm assuming that I'll be able to follow your proof as you had only highschool training at the time

I'll also look forward to sharing it with my grade 12 Data Management class, where I actually discuss the theorem with the class (briefly)

L8R

Pete

hhEb09'1

2005-Sep-16, 02:18 PM

I've since given talks on why the current attempts to solve the problem are not trying to solve the problem, but rather trying to rename it. I've also taken the obligatory cheap shots at computers used in a supposed proof. I notice in your resume (http://www.geocities.com/davidmadison01/david500.htm) that you say yours is the only proof so far. Why do you discount the one by Appel and Haken (cite (http://www.math.gatech.edu/~thomas/FC/fourcolor.html)--and I notice they say they have another proof)?

worzel

2005-Sep-16, 03:57 PM

I notice in your resume (http://www.geocities.com/davidmadison01/david500.htm) that you say yours is the only proof so far. Oh that's up now. I came across it in google the other day but it was down.

Wish I had a resume like that, you know, pretty normal really, up until the last line of other interests, "Oh yeah, and I'm the only person to have proved fermat's last theorem in the space of a margin."

Hope Phil agrees to supporting your authorship, Madad.

Maddad

2005-Sep-16, 11:59 PM

I notice in your resume (http://www.geocities.com/davidmadison01/david500.htm) that you say yours is the only proof so far. Why do you discount the one by Appel and Haken (cite (http://www.math.gatech.edu/~thomas/FC/fourcolor.html)--and I notice they say they have another proof)?Valid question. As mentioned in that page, that proof is not satisfactory.

There are a number of reasons that a computer cannot support any proof of the theorem. The problem starts because the logic is faulty. If I told you that my good friend Fred who lives in the apartment down the street is really smart, has worked on the thorem a long time, and has been unable to solve it, would you accept that as proof that a map needs no more than four colors? I don't think so. You would say that you have no way of knowing what methods Fred tried, why he even thinks it can't be done, and since you have no way of knowing the method he used, you cannot ensure that he didn't skip some important step, smart as he is or not (or so I claim). There is no way to get the same answer that Fred did, so the reproducibility requirement of science is left unsatisfied. Even if he's tried and failed, we have no way to tell that he he finished looking, so we have no way to tell if he would solve it by putting in another five minutes of study.

A computer proof suffers from exactly the same problem, plus some others. Who wrote the program that performed the solution? Did he write it accurately, or did he fall victim to GIGO? Remember that nobody has checked the answer because it is too big, so in effect we have no reproducibility. Was the method used by the programmer capable of testing the problem? All you know is that some progammer somewhere thinks so. Has there ever been an error in programming anywhere in the history of computing? How do you know one of them didn't show up here? Was his computer search exhaustive enough? The programmer claims so, but how do you actually know since his work cannot be checked? And what about hardware failures? Some of you may remember the difficulty with the original pentium that inaccurately performed some obscure mathematical calculations. Intel had to recall those processors and replace them with ones that had been fixed. Could such a problem ever happen agin? You say no? How do you know that, for certain, when you must know that for certain to say that the problem has been proved? Suppose that this is not the first time that microprocessors have been manufactured and sold that incorrectly performed math operations? If the original Pentium was the second offence, not the first, would you worry a bit more that such a problme MIGHT arise again? While you probable are familiar with the inadequacy of the original Pendium, few people remember that the 386 chip had a similar problem that went undetected until the release of Autocad 10. Intel went to work, fixing the problem, and released a replacement processor, which makes the Pentium problem the second time around. But it's not even the second time, because Intel botched the repair. Their fix was still broken, so they had to release yet a third version of the 386 to get it to quit making math errors.

This track record with computer hardware is stark explanation of why a computer cannot be used to prove the Four Color Map Theorem. The problem though is even bigger. Had the computer drawn the desired map in which five territories each touched another, it still would not have prooved the problem. Can anyone guess why?

Maddad

2005-Sep-17, 12:01 AM

Hope Phil agrees to supporting your authorship, Madad.He strongly advised against it. Suggested that I submit it to an official publication somewhere for peer review. I don't know who might take it though.

cfgauss

2005-Sep-17, 05:44 AM

There are a number of reasons that a computer cannot support any proof of the theorem. The problem starts because the logic is faulty. If I told you that my good friend Fred [..............]

Ya, too bad we don't, you know, write down what we tell our computers to do. If only there was some kind of "code" we could write, that was algorithmic, and other people could check...

A computer proof suffers from exactly the same problem, plus some others. Who wrote the program that performed the solution? Did he write it accurately, or did he fall victim to GIGO?

If only other mathematicians would develop and learn this "code" they could check it so easily...

Has there ever been an error in programming anywhere in the history of computing? How do you know one of them didn't show up here? Was his computer search exhaustive enough? The programmer claims so, but how do you actually know since his work cannot be checked?

And if only the program was only made to show us its work instead of just printing "proved" or "not proved".

And what about hardware failures? Some of you may remember the difficulty with the original pentium that inaccurately performed some obscure mathematical calculations. Intel had to recall those processors and replace them with ones that had been fixed.

Hardly obscure... they knew about it when they began making them. They just assumed (rightly) that the error would be small enough that it wouldn't effect most people.

Could such a problem ever happen agin? You say no? How do you know that, for certain, when you must know that for certain to say that the problem has been proved?

[.................................................]

And if only they could some how use this hypothetical "code" to check if the program gave the same "proved" or "not proved" answer on systems with different components...

Maddad

2005-Sep-17, 04:38 PM

Ok, the last part of that long post asked the question, "If someone drew a satisfactory map with five colors, why would it not prove the theorem?"

jfribrg

2005-Sep-18, 02:07 AM

Ok, the last part of that long post asked the question, "If someone drew a satisfactory map with five colors, why would it not prove the theorem?"

Because the theorem states that it can be done with 4. It had been known for a century or more IIRC that 5 is sufficient. Just because it can be done with 5 doesnt prove that it can be done with 4.

worzel

2005-Sep-18, 09:00 AM

Ok, the last part of that long post asked the question, "If someone drew a satisfactory map with five colors, why would it not prove the theorem?"Actually, what you asked was:

Had the computer drawn the desired map in which five territories each touched another, it still would not have prooved the problem.If the computer, or anyone else for that matter, drew a map where five territories each touched one another then wouldn't that disprove the four color theorem.

hhEb09'1

2005-Sep-18, 10:57 AM

If the computer, or anyone else for that matter, drew a map where five territories each touched one another then wouldn't that disprove the four color theorem.Yes. A map with all five countries touching each other would mean that five colors would be needed, and the theorem would be false. "Touching" of course means sharing a length of border, not just a point (as all pieces of a pie do).

Martin Gardner once wrote a short story where the main character was told about an island where all five divisions of the island touched each other. He was OK with that since the Four Color Theorem had not been proved (even though it had been shown without computers that just five countries could not touch each other), but after exploring the island and verifying the claim, he was shocked when he suddenly realized that the ocean was a sixth region that touched all the other five.

Maddad

2005-Sep-18, 09:11 PM

If the computer, or anyone else for that matter, drew a map where five territories each touched one another then wouldn't that disprove the four color theore.The problem is that the person doing so would immediately be asked, "Hey, if you can draw a map with five colors, could you do it with six?" The new celebrity would scatch his head, mutter something about five being hard enough, and maybe give it a try. People would be talking about the new Five Color Map Theorem

The problem is that success at drawing the map doesn't solve the real problem; it just changes the name. The real problem is to establish the upper limit in colors.

The irony is that both success and failure in drawing the map result in failure of a meaningful proof.

ASEI

2005-Sep-18, 09:19 PM

If you want to prove the four color theorem, you could try to construct a proof as follows:

Assuming that a map requires more than four colors, it would have to have five seperate regions each capable of touching each of the other four regions by an independent route on a 2-d surface.

An analogy would be using five points to symbolize the regions, and non-intersecting lines to symbolize the connections touching each region. Can you get all five to tough all other four points? (4 connections/point, 20 total?)

I doodled a lot of these, but couldn't find any way to get all five points to connect to all their necessary neighbors.

A proof of the four color theorem could work the same way, assuming all possible combinations are tried.

worzel

2005-Sep-18, 11:44 PM

Maddad, I am totally confused about what you are trying to say [ subtext being I think you are totally confused :) ].

The problem is that the person doing so would immediately be asked, "Hey, if you can draw a map with five colors, could you do it with six?" The new celebrity would scatch his head, mutter something about five being hard enough, and maybe give it a try. People would be talking about the new Five Color Map TheoremThat's just silly. If you have proved it for 5 colours then you have proved it for 5 or more colours. The theorem is that at most 4 colours are needed, not that you can't do it with more colours if you like. If it is proven that 5 suffice, then we know that we can take any map and randomly select one region and instead colour it with a 6th colour. Ditto for 7, all the way up to n colours for n regions, which is trivial of course.

The problem is that success at drawing the map doesn't solve the real problem; it just changes the name. The real problem is to establish the upper limit in colors.What do you mean by "success at drawing the map"? The theorem is not that there exists a map such that... and the proof, therefore, is not simply an example of such a map. The theorem is that for all maps, 4 colours suffice. The real problem was to establish the lower limit of colours needed, which has now been proven to be 4 (it's easy to come up with a counter example for 3 colours).

The irony is that both success and failure in drawing the map result in failure of a meaningful proof.Let's get this straight:

A proof that 5 colours suffices for any map proves that 6,7,...,n colours also suffice but says nothing about 4 colours.

A proof that 4 colours suffice for any map proves that 5,6,7,...n colours also suffice and subsumes any proof for any number > 4.

An example of a map coloured with 5 colours (which is what you seem to be getting at) says nothing except that 5 colours suffice for that one example.

A map which has five regions which all share common boundaries with each other would disprove the 4 colour theorem because it is a counter example that requires at least 5 colours. As the 4 colour theorem has been proved, no such map exists.

Do you disagree with any of those?

I'm sorry if I seem to be stating the blindingly obvious, but for someone who claims to have proven the four colour theorem you don't seem to have much of a grasp of what the theorem says. Hopefully I just misunderstood you.

worzel

2005-Sep-18, 11:51 PM

Martin Gardner once wrote a short story where the main character was told about an island where all five divisions of the island touched each other. He was OK with that since the Four Color Theorem had not been proved (even though it had been shown without computers that just five countries could not touch each other), but after exploring the island and verifying the claim, he was shocked when he suddenly realized that the ocean was a sixth region that touched all the other five.Was the island inhabited by Tauruslanders? :)

Maddad

2005-Sep-20, 10:48 PM

Maddad, I am totally confused about what you are trying to say. . . If you have proved it for 5 colours then you have proved it for 5 or more colours.Yes, proving the FCMT for four colors also proves it for five or more. However, current attempts to deal with the FCMT involve trying to draw the map. Should that attempt succeed, then it would disprove the FCMT. I can see why you were confused by my post; I wasn't clear on that. If you have disproved the FCMT in four colors by drawing such a map, it does not necessarily disprove it for five or more.

What do you mean by "success at drawing the map"?People are trying to draw a map that does display five territories, each of which touches the other four in an arc or line segment. If they succeed, then they have disproved the FCMT. If they fail, then the results are indeterminant.

Now, are we both on the same page, and do you agree with the following:

1. A computer program that says it proves you cannot draw a five color map is insufficient proof of the problem.

2. Success at drawing a map with five territories simply renames the problem to the Five Color Map Theorem rather than establishing the maximum number of colors that you might have to use.

worzel

2005-Sep-20, 11:57 PM

Yes, proving the FCMT for four colors also proves it for five or more. However, current attempts to deal with the FCMT involve trying to draw the map. Should that attempt succeed, then it would disprove the FCMT. I can see why you were confused by my post; I wasn't clear on that. If you have disproved the FCMT in four colors by drawing such a map, it does not necessarily disprove it for five or more.

People are trying to draw a map that does display five territories, each of which touches the other four in an arc or line segment. If they succeed, then they have disproved the FCMT. If they fail, then the results are indeterminant.

Now, are we both on the same pageYes, I agree with all of that so far, if we assume for the moment that the FCMT is not yet proved.

and do you agree with the following:

1. A computer program that says it proves you cannot draw a five color map is insufficient proof of the problem.No, I strongly disagree. cfguass made some good points about this.

I would go as far as to say that a formal system of logic is, by definition, a system that can be computerised. The axioms and rules of inference give us all we need to write a theorem prover. If the code is correct (it can be checked by mathematicians just like any formal system can) and the computer executes it correctly (the result can be checked on many different architechtures) then it is safe. You may have some philosophical problems with it, but for me it is no different to using a calculator to compute some of the arithmetic in the proof. Indeed, Godel showed how one can turn each step of a proof into an arithmetical statement. That is not to say that finding the proof is algorithmic, Godel had something to say about that as well :)

IIRC computerised theorem proving wasn't even what was used for the FCMT. The non-computerised part (the bit I presume you'd be happy with) was to show that any map can be reduced to an equivalent map (for the purposes of the theorem) from a finte set. The computer then simply checked that each one of these maps could be coloured with only four colours. Proving something for a finite number of cases can be done by brute fource and is very different to proving something for an infinte number of cases. Assuming the code has been checked and the results verified, the program did undeniably colour each case with only four colours.

2. Success at drawing a map with five territories simply renames the problem to the Five Color Map Theorem rather than establishing the maximum number of colors that you might have to use.Yeah, I guess it would. But that's rather moot as the Four Colour Map Theorem has already been proven - so any search for a map with five pairwise neighbouring regions is doomed to failure. As you claim to have proven the FCMT yourself, presumably you agree with this even if you are not convinced by the generally accepted proof.

hhEb09'1

2005-Sep-21, 05:42 PM

People are trying to draw a map that does display five territories, each of which touches the other four in an arc or line segment. If they succeed, then they have disproved the FCMT. If they fail, then the results are indeterminant.They will always fail. It is fairly easy to prove that five territories cannot each touch the other four.

Now, are we both on the same page, and do you agree with the following:

1. A computer program that says it proves you cannot draw a five color map is insufficient proof of the problem.

2. Success at drawing a map with five territories simply renames the problem to the Five Color Map Theorem rather than establishing the maximum number of colors that you might have to use.Not "renames" the problem. It would no longer be a problem, since it was proven that five is sufficient long before computers even. :)

But, as I said, it would take much more than just a map of five territories. Link (http://mathworld.wolfram.com/Four-ColorTheorem.html)

Maddad

2005-Sep-22, 03:02 AM

the Four Colour Map Theorem has already been proven - so any search for a map with five pairwise neighbouring regions is doomed to failure. . . . presumably you agree with this even if you are not convinced by the generally accepted proof.It's finding a starting point in your post is difficult because I have a great many choices. I'm going to pick a couple.

The problem with a computer proof is not philosophy; it's that we are unable to know, to the level necessary to claim proof of the Theorem, that the computer did in fact perform it's calculation correctly. Maybe you quickly passed over my original reasoning, but we are unable to know that the code is correct because we are unable to be sure that the microcode in the processor is not flawed. Remember, we have not one, but three prior instances in which this microcode later turned out to be defective.

I am glad that you brought up reduction of a map from a finite set as part of a proof. I used a reverse process in developing my own proof. I do not need a computer; I never exceed two possibilities for where and how a new teritority might be positioned and connected. One side of an 8½ x 11 sheet of paper will do. If you're using a computer for selecting one of two possibilities, you're in league with my mother-in-law.

worzel

2005-Sep-22, 08:43 AM

The problem with a computer proof is not philosophy; it's that we are unable to know, to the level necessary to claim proof of the Theorem, that the computer did in fact perform it's calculation correctly. Maybe you quickly passed over my original reasoning, but we are unable to know that the code is correct because we are unable to be sure that the microcode in the processor is not flawed. Remember, we have not one, but three prior instances in which this microcode later turned out to be defective.You've restated what you said originally but haven't answered cfgauss's points. If a microcode bug affected the program in anyway then it wouldn't run consistently on different platforms.

I am glad that you brought up reduction of a map from a finite set as part of a proof. I used a reverse process in developing my own proof. I do not need a computer; I never exceed two possibilities for where and how a new teritority might be positioned and connected. One side of an 8½ x 11 sheet of paper will do.Well it shouldn't be too hard to knock up a webpage explaining it then :)

Maddad

2005-Sep-22, 06:57 PM

I've addressed them several times now. The code can run consistently on several platforms; it can also run consistently incorrectly. We are unable to know that such code contains no error. Yes, mathematicians could check the code easily, if you say to them, "We think this is the specific microcode error that exists." However, if you instead say to them, "Verify that no error whatsoever exists in this microcode", then it's no longer so easy to verify. If it was so easy to verify, why did Intel have such an error three times? And if they had it three times, how do you know that there is not a fourth example of it?

If you cannot accept that computer participation in the Four Color Map Theorem invalidates the solution, then there is not point in my continuing to demonstrate a proof here that avoids the problem.

worzel

2005-Sep-22, 10:28 PM

I've addressed them several times now. The code can run consistently on several platforms; it can also run consistently incorrectly. We are unable to know that such code contains no error. Yes, mathematicians could check the code easily, if you say to them, "We think this is the specific microcode error that exists." However, if you instead say to them, "Verify that no error whatsoever exists in this microcode", then it's no longer so easy to verify. If it was so easy to verify, why did Intel have such an error three times? And if they had it three times, how do you know that there is not a fourth example of it?Remember that the microcode is not part of the proof, it does not port with the code from one platform to another. A mathematician checking the code is checking the algorithm that does port, not the microcode of each chip it is ported to. The algorithm has not only been checked, but improved and reimplemented in different languages, and then run with equivalent output.

If I were charged with programming this task, I would have the code output how it dealt with each configuration, not just a "yes" or "no". If the output matched on different architectures then the chances of there being an error in the microcode of each chip used in just such a way that it affected each execution of the code on those different platforms in just such a way as to produce identical output is astronomically small. I'm sure the smart people who have done all the checking did something at least as thorough, why wouldn't they? Finding a genuine error in the proof would gain one far more notoriety than confirming it.

If you cannot accept that computer participation in the Four Color Map Theorem invalidates the solution, then there is not point in my continuing to demonstrate a proof here that avoids the problem.If you won't present your proof then there is little point carrying on the discussion. An elegant proof would obviously be highly desirable whatever one thinks of the current proof - sounds to me like you're trying to weasel out because you know your proof is flawed. If I'm wrong, prove me wrong, present your proof!

peter eldergill

2005-Sep-23, 01:19 AM

Could it be argued then along the same lines that Euclidean Geometry is not valid either because he based it on "postulates" (or assumptions)? Like parallel lines never meet and others (Sorry, I can't remember...I thought there a five postulates he had, some of which have been shown to be equivalent?

I agree with Worzel about a traditional proof. This would be fantastic, but since none exists (until Maddad supplies us with one, that is :surprised ), I will accept the computer proof.

Pete

montebianco

2005-Sep-23, 01:29 AM

Could it be argued then along the same lines that Euclidean Geometry is not valid either because he based it on "postulates" (or assumptions)?

Won't get far without postulates :)

Like parallel lines never meet and others (Sorry, I can't remember...I thought there a five postulates he had, some of which have been shown to be equivalent?

Some info here.

http://www.health.uottawa.ca/biomech/csb/laws/euclid.htm

There have been attempts to prove that the fifth postulate is redundant, but it is now known that this cannot be done, and systems of geometry in which the fifth postulate is false have been developed.

I agree with Worzel about a traditional proof. This would be fantastic, but since none exists (until Maddad supplies us with one, that is :surprised ), I will accept the computer proof.

Pete

It fits on a couple of sheets of paper? If such a thing exists, then who cares about a computer proof.

peter eldergill

2005-Sep-23, 01:42 AM

Quote:

Originally Posted by peter eldergill

Could it be argued then along the same lines that Euclidean Geometry is not valid either because he based it on "postulates" (or assumptions)?

Won't get far without postulates

That's what I was trying to get at I think, don't we have to assume that the computer works well enough to prove this? I would trust the word of the chip designer if that's their claim (i.e. I will take the word of the expert)

Pete

peter eldergill

2005-Sep-23, 01:45 AM

Some info here.

http://www.health.uottawa.ca/biomec...laws/euclid.htm

There have been attempts to prove that the fifth postulate is redundant, but it is now known that this cannot be done, and systems of geometry in which the fifth postulate is false have been developed.

Are Hilbert's spaces then more complete than Euclids (in terms of missing assumption in the axioms?)

Pete

montebianco

2005-Sep-23, 02:45 AM

That's what I was trying to get at I think, don't we have to assume that the computer works well enough to prove this? I would trust the word of the chip designer if that's their claim (i.e. I will take the word of the expert)

Pete

Well, we would have to assume that, but I think that's the issue here. At least one person here objects to this as an axiom (I don't particularly like it myself :))

montebianco

2005-Sep-23, 02:51 AM

Are Hilbert's spaces then more complete than Euclids (in terms of missing assumption in the axioms?)

Pete

It would appear so, but I'm way out of my element here. A Hilbert space to me means something rather different (an infinite-dimensional vector space with an inner-product, maybe some other requirement that I've forgotten) :)

peter eldergill

2005-Sep-23, 03:33 AM

I thought Hilbert Spaces were finite dimensional (usually). Or perhaps hyperdimensional? Ha!

I recall a geometry prof starting many theorems with "Let V be a finite dimensional Hilbert space with an inner product", but I never even knew that Hilbert had more accurate axioms for geometry

Pete

peter eldergill

2005-Sep-23, 03:35 AM

Well, we would have to assume that, but I think that's the issue here. At least one person here objects to this as an axiom (I don't particularly like it myself )

Reply With Quote

Isn't a large chunk of chaos theory (dynamical systems) done with the aid of computers?

Should we also abandon all of that?

Pete

montebianco

2005-Sep-23, 04:06 AM

Isn't a large chunk of chaos theory (dynamical systems) done with the aid of computers?

Should we also abandon all of that?

Not of any particular interest to me, but why do you seem to suspect that I feel it should be abandoned?

montebianco

2005-Sep-23, 04:14 AM

I thought Hilbert Spaces were finite dimensional (usually). Or perhaps hyperdimensional? Ha!

I don't usually think explicitly in Hilbert space terms, but I do recall reading a book (it was March 2003, I remember where I was when I read it and I've only been there once) which defined them as necessarily infinite-dimensional. I also recall thinking that that was odd...but certainly, the space of L-2 integrable functions on the real line is a common example of a Hilbert space, and that's infinite-dimensional.

I recall a geometry prof starting many theorems with "Let V be a finite dimensional Hilbert space with an inner product", but I never even knew that Hilbert had more accurate axioms for geometry

I didn't either. He did quite a lot though, including, I think coming up with the first solution to the field equation of Einstein, even before Einstein did - but perhaps I am mistaken, perhaps it was derivation of the equation itself. Or maybe I'm completely misremembering...

HenrikOlsen

2005-Sep-23, 05:11 AM

(Sorry, I can't remember...I thought there a five postulates he had, some of which have been shown to be equivalent?

He had 5 postulates.

You can draw a straight line from any point to any point

you can continue a line to infinity

you can contruct a circle with any center and any radius

all right angles are equal to one another

If a straight line falling on two straight lines make the interior angles on the same side less than two right angles, the two straight lines, if extended indefinitely, meet on the side on which are the angles less than two right angles.

None of these can be derived from the others.

People had been trying to derive the 5th from the others for millenia until it was shown that it couldn't be done by generating internally consistent geometries using other propositions

peter eldergill

2005-Sep-23, 01:10 PM

Not of any particular interest to me, but why do you seem to suspect that I feel it should be abandoned?

I mentioned this due to the recent discussion about possible flaws in the computer processors

Pete

hhEb09'1

2005-Sep-23, 06:41 PM

I don't usually think explicitly in Hilbert space terms, but I do recall reading a book (it was March 2003, I remember where I was when I read it and I've only been there once) which defined them as necessarily infinite-dimensional. I also recall thinking that that was odd...but certainly, the space of L-2 integrable functions on the real line is a common example of a Hilbert space, and that's infinite-dimensional.Hilbert spaces can be infinite dimensional, but there are finite dimensional Hilbert spaces (cite (http://mathworld.wolfram.com/HilbertSpace.html)).

Maddad

2005-Sep-25, 11:32 PM

Remember that the microcode is not part of the proofIt most certainly is! The person running the progrogam interfaces to what the programer wrote. That sits on top of the program that compiled the program, which in turn rests on the operating system. The entire shooting match talks to the microcode, which means that the microcode is the most fundamental part of the proof offered by a computer program.

Porting to a new chip bring up a new microcode set, to be sure, but now you're needing to examine the validity under multiple systems for errors of unknown quality. Not only have we not positively researched the first microcode set; we sure as shootin' haven't compared the results against a second set. While much of the microcode is identical from one manufacturer to the next, there are differences if for no other reason than to avoid copyright infringment issues. Howsomever, because the ultimate job of the microcod of one processor is essentially identical to the job of another, it must be very close. If errors exist, they may be conceptual errors that both systems share.

Worzel, you're a smart guy, and I'm not telling you anything you don't already know. You have to be operating on an emotional inability to deal with the issue to keep missing such a basic issue.

there is little point carrying on the discussion.I agree. If we cannot get past these basics, then the logic reversals in the proof will indeed be too confusing to understand.

Could it be argued then along the same lines that Euclidean Geometry is not valid either because he based it on "postulates" (or assumptions)?No sir.

That's what I was trying to get at I think, don't we have to assume that the computer works well enough to prove this? I would trust the word of the chip designer if that's their claim (i.e. I will take the word of the expert)Establishing oroofs is not about accepting the word of an expert.

montebianco

2005-Sep-26, 12:50 AM

Hilbert spaces can be infinite dimensional, but there are finite dimensional Hilbert spaces (cite (http://mathworld.wolfram.com/HilbertSpace.html)).

That's what I would have thought, but after the post I made above, I even went and checked my book, and it does indeed say necessarily infinite-dimensional! I remember thinking this was odd at the time.

Arg, now I have to check again because I can't remember who the author is...

montebianco

2005-Sep-26, 12:56 AM

I mentioned this due to the recent discussion about possible flaws in the computer processors

Pete

I'm not suggesting abandoning anything. I just don't like adding "The computer works properly" to a list of axioms. In a rigorous logical system with a well-defined notion of truth and falsity, then the axioms determine the truth or falsity of a statement, independently of any proof. The proof tells us whether it is true or false, but it was true or false before we came up with the proof; we just didn't know it. I just wouldn't want to add "The computer works properly" to a list a fundamental axioms, anymore than, for a proof done without a computer, I would want to add "The person who wrote the proof and the people who have checked it didn't make any mistakes."

This was the intended meaning of my earlier statement.

Grey

2005-Sep-26, 01:47 AM

I agree. If we cannot get past these basics, then the logic reversals in the proof will indeed be too confusing to understand.

Regardless of what Worzel thinks, I'd be very interested to see your proof. Either it has a flaw in it, which will be interesting to track down, or it's valid, in which case I'd fly out to see Pace eat his hat. :)

peter eldergill

2005-Sep-26, 02:07 AM

Bring it on! Then I can pretend to understand it!

Pete

hhEb09'1

2005-Sep-26, 04:59 AM

If you're so willing to spring for the fare, I'd fly there :)

worzel

2005-Sep-26, 08:51 AM

Worzel, you're a smart guy, and I'm not telling you anything you don't already know. You have to be operating on an emotional inability to deal with the issue to keep missing such a basic issue.I'm afraid you're missing a very basic point. The microcode on different architechtures is completely different. The same program written in 'c', say, would even compile to different machine codes on different architectures - how could they possibly share microcode? If the same program written in a high level language is compiled for, and executed on, differing archictures and produces identical output, then if that output is quite verbose the odds of there being a microcode bug on each architecture which affected the outputs identically is astronomically small. Moreover, the algorithm has been reimplemented in different languages, and improved algorithms have also been developed. Guess what, they all confirm the result.

I put it to you, Maddad, that you have an emotional inability to let go of what was a temporary doubt with the current proof because you wish to cling on to your fantasy that you are the first to prove it.

I agree. If we cannot get past these basics, then the logic reversals in the proof will indeed be too confusing to understand.Nonsense. The only thing stopping us from discussing your proof is the lack of your proof. As both I and Grey have stated, what I think of the current proof is irrelevant to your proof. You claim to have come up with it while stil at school and claim that it fits on a sheet of A4 so I am pretty confident that my feeble mind can deal with it. But even if it is beyond me, I can assure you that both Grey and hhEb09'1 are more than up to the task and are both eager to see your proof.

Celestial Mechanic

2005-Sep-26, 05:50 PM

The problem with a computer proof is not philosophy; it's that we are unable to know, to the level necessary to claim proof of the Theorem, that the computer did in fact perform it's calculation correctly. Maybe you quickly passed over my original reasoning, but we are unable to know that the code is correct because we are unable to be sure that the microcode in the processor is not flawed. Remember, we have not one, but three prior instances in which this microcode later turned out to be defective.

I've addressed them several times now. The code can run consistently on several platforms; it can also run consistently incorrectly. We are unable to know that such code contains no error. Yes, mathematicians could check the code easily, if you say to them, "We think this is the specific microcode error that exists." However, if you instead say to them, "Verify that no error whatsoever exists in this microcode", then it's no longer so easy to verify. If it was so easy to verify, why did Intel have such an error three times? And if they had it three times, how do you know that there is not a fourth example of it?

But what assurance do we have that mathematicians have performed their calculations and logic correctly? In the case of the four-color theorem, there was a proof published by Kempe in 1879 that stood for 11 years before Heawood gave a counter-example and re-opened the problem in 1890. The chances are very good that your proof likewise has a small logic error, something easily overlooked. No one will ever know until your proof is submitted to review.

As for your three examples, I know that one of them was in floating-point division (something not likely to be used in a combinatorics problem like the four-color theorem), but I don't think the others were in arithmetic. (But please correct me if they were!) I think the others were technical things that affected operating system functionality but not arithmetic. The odds of a computational bug is very small precisely because so many results are known precisely and we can verify the results we get.

jfribrg

2005-Sep-26, 07:04 PM

One thing I haven't seen mentioned is that there is ongoing research into mathematical proofs of program correctness. I haven't dealt with it since grad school, so I can't give an example until I dig up my old books on the subject, but in general it is possible to prove that certain types of programs are correct. The problem here is that it has been proven that real-time systems cannot be proven correct, so the issue of the microcode becomes the main theoretical stumbling block. I have not been able to find any references to prove the correctness of the 4 color theorem ( I didn't look too hard either). I think this can be done in 3 steps:

1) Prove that the algorithm is correct ;

2) Prove that the RISC implementation of the program matches the algorithm

3) build a special purpose RISC computer that runs the program and nothing else. Specifically, this computer can have no interrupts, and the only output is a binary value. This last step may seem far-fetched but is necessary in order to complete the proof.

I am not sure if the theory of program correctness proofs has matured enough to handle something as complex as the 4 color theorem, but I don't see any reason why it couldn't be done, especially if we use an automated theorem proving program to do step 1 for us. That may sound like a circular argument (using a computer to prove that a computer proof is correct), but it isn't since the ATP output can be hand checked.

I know this is a rambling post, and I will make additional posts in the near future to clarify these ideas.

Maddad

2005-Sep-26, 09:15 PM

Regardless of what Worzel thinks, I'd be very interested to see your proof. Either it has a flaw in it, which will be interesting to track down, or it's valid, in which case I'd fly out to see Pace eat his hat. :)Ok. I told myself that I'd post it if there was one person interested. You're it.

Our initial world will be a limited two dimensional surface--a sheet of paper. We will arrange territories so that they do not border each other directly, but rather we represent their border by drawing a line to connect them. A border between two territories may not cross the border between another two. We'll represent the territories by simplifying their shapes to a circle. When we add the first territory to the new map, there is only one possible place to put it. On the map.

Grey, are you Ok with my reduction of territory shapes to circles and representing borders between them with connecting lines? I don't know if I need more explanation here or not.

hhEb09'1

2005-Sep-26, 10:18 PM

Grey, are you Ok with my reduction of territory shapes to circles and representing borders between them with connecting lines? I don't know if I need more explanation here or not.I don't think there should be any problem with that. I think that's actually the usual way of representing the regions.

Grey

2005-Sep-27, 12:48 AM

Grey, are you Ok with my reduction of territory shapes to circles and representing borders between them with connecting lines? I don't know if I need more explanation here or not.That's just fine. As Pace pointed out, most mathematical treatments of the question generally use the same method.

snarkophilus

2005-Sep-27, 11:27 AM

You can do simple tests to see whether or not the basic electronics function properly. It is not hard. I remember doing it in a second year hardware course. This is always done at the factory, of course.

Of course, you might argue that random data corruption might skew your results. This happens rather frequently, in fact. Little static discharges in the air and across circuit boards change data all the time. However, we have error-correcting mechanisms built into machines that make the chances of an error in a processor not being picked up very small indeed. Also, these errors are not reproducible, and are weeded out when you run the programme again.

Or maybe your OS is bad, and it changes your data in some way. Run under two OS's, because there is almost no way that such an error would exist in two separate products. If you're really paranoid, build your own OS, one whose correctness can be proven (and this can be done).

All that's left is the algorithm and the logic of the proof itself, which have been rigorously checked.

Look at it this way. Treat the computer as a scientifically studied object. If, after determining that the chance of getting bad results is less than, say, 10^-12 (which is much worse than data corruption going undetected at the hardware level, and much worse than the same corruption happening the same way on two machines), you can't trust your computer to do its calculations correctly, then you can't trust anything. You can't trust pictures you get from Hubble. You can't trust the clock on your wall. You can't trust that the food in your stove is being cooked at a high enough temperature, or that you are even reading this right now and not imagining it. All of those things have errors worse than those of a properly built computer. Very smart people have thought of these things, and they've built in safeguards.

All in all, a proof being false as a result of massive, widespread machine failure is far less likely than my going insane and just imagining that the proof was false. I'm willing to go out on a limb here and say that it's probably fine.

(As an aside, the Pentium arithmetic problem was a big deal for a couple of people I know... they did not know about it prior to buying machines, and ended up having to re-run several thousand hours of simulations. So now they build pretty comprehensive test programmes to run on any machine before using it for scientific purposes.)

Maddad

2005-Sep-27, 08:52 PM

Snark

That approach works if we are looking for the kind of error the system exhibits. If it has a different kind of error then we would not be successful.

Grey

Ok. When you introduce the second territory on the map, there is also only one possible place you can put it. Somewhere else. I like to keep the separation between them at least several territory diameters, but that is only an issue of taste. If you make the distance much less, then as your map becomes triangular it becomes unnecessarily crowded when you add another internal territory. If you make the disconnection too great, then the diagram can become ungainly. I also like to think of the line connecting the two territories as slightly thicker than a simple pencil line, but again this does not affect the outcome of the problem whatsoever. Thin works just fine.

What you wind up with is a dumbbell appearance. Two circles separated by a bar. I think of the dumbbell as being horizontal, roughly centered on the page, but it will function identically if you draw it vertically or even diagonally.

Ok, before we introduce our third territory, do you have any questions?

Grey

2005-Sep-28, 01:34 AM

Ok, before we introduce our third territory, do you have any questions?Nope. Looks good so far.

jfribrg

2005-Sep-28, 01:44 PM

I recall a few years ago someone an empirical demonstration of the 4 color theorem by using a "chemical computer", using amino acids. By combining different amino acids in a solution, if four colors were not sufficient, then certain types of proteins would be produced. After combining them, no such proteins were found. Its not exactly a proof, but since many trillions of molecules were used in the solution, the correctness of the theorem is very compelling. Combine that with the other proofs and it becomes very difficult to argue that the theorem is wrong. One may still argue that it is not rigorously proven (others would disagree), but to argue that it is false is a very difficult position to support.

Grey

2005-Sep-28, 02:02 PM

I recall a few years ago someone an empirical demonstration of the 4 color theorem by using a "chemical computer", using amino acids. By combining different amino acids in a solution, if four colors were not sufficient, then certain types of proteins would be produced.Do you have a reference for this anywhere? I'm fascinated by the notion of being able to correlate the creation of certain types of proteins to the falsity of the four color theorem, and I'd really like to see how they did it.

Maddad

2005-Sep-28, 09:41 PM

When you add a third territory, you appear to have two choices. You may put the new territory either to one side of the dumbbell, or you may put it above or below. These though will turn out to be the same.

For the first case, place the third territory centered above the dumbell such that the three territories form an equallateral triangle. Draw in the remaining two sides of the triangle, which now represent the borders between this new territory and the first two territories. Note that had you placed the new territory below the dumbbell instead of above it, then you would produce an upside-down triangle which would function as a map identically to being rightside-up.

In the second case, slide the dumbbell over to the left and place the third territory to the right of the dumbbell such that the left side and right side territories are equally as far from the center territory. Draw a line from the new territory to the center territory, representing the border between them. Now draw a curved line between the two outside territories that passes under the center territory without touching it. All three territories now border each other.

Get out a hammer and torch and heat the two straight lines. Then beat the two outside territories with the hammer, driving them down below the horizontal position of the center territory. The two straight lines now angle down and to the sides from the center, and the curve of the bottom line is more exaggerated. Keep hammering until the angle between the two straight lines at the center territory is 60 degrees. Now straighten out the bottom curved line between the two outside territories; it will not touch the center one. You now have another equallateral triangle with circular territories at the corners, which is identical to the first case.

Ready for territory number four?

Maddad

2005-Sep-28, 10:21 PM

At this point we should be confident that we have a diagram representing every possible arrangement of three territories on a limited two dimensional surface. If you have lost this orientation during the building, then let me know so that we can all be on the same page.

01101001

2005-Sep-28, 11:56 PM

Get out a hammer and torch and heat the two straight lines. Then beat the two outside territories with the hammer, driving them down below the horizontal position of the center territory. The two straight lines now angle down and to the sides from the center, and the curve of the bottom line is more exaggerated.

This is a mathematically rigorous proof?

Can we just stipulate that all planar graphs of 4 nodes are four-colorable and move on from there to all remaining planar graphs?

peter eldergill

2005-Sep-29, 02:00 AM

Maddad, have you studied graph theory? You are describing edges and veritices, specifically the complete graph of 3 vertices, K3 (the 3 is subscript). It is a planar praph, meaning that it can be redrawn in a way so that no edges cross.

A complete graph means that every vertex is connected to every other vertex with exactly one edge.

I'm not sure where you're going with this yet, but K4 (complete graph with 4 vertices) is also planar, but K5 is not planar.

If you haven't studied graph theory, I think you would enjoy it, and I suggest you pick up any standard introduction to the subject (Bondy and Murty is a standard as I recall)

Pete

Edit: The graphs you have describes in case 1 and 2 are called isomorphic, and I don't think it is necessary to distinguish them, especially in terms of graph theory. An edge is only defined by it's associated vertices, not length, curvature, etc...

peter eldergill

2005-Sep-29, 02:08 AM

01101001.....(I had to check that I got your name right about 4 times!)

In terms of planar graphs/colouring and in graph theory terms, what exactly are we trying to prove?

Pete

Joff

2005-Sep-29, 02:17 AM

The four colour theorem. Sshhh, it's going to get interesting soon. I think he's going to add a fourth vertex and join it to the other three.

Grey

2005-Sep-29, 12:54 PM

Ready for territory number four?Yes, please. You're welcome to move a little faster, if you'd like. I can always ask you to slow down when things get complicated.

hhEb09'1

2005-Sep-29, 04:20 PM

At this point we should be confident that we have a diagram representing every possible arrangement of three territories on a limited two dimensional surface. If you have lost this orientation during the building, then let me know so that we can all be on the same page.That is not quite true. For instance, one could have three territories side by side. The graph would have three circles in a row, joined by just two lines.

I have a feeling that that is not going to make a difference in your proof, but who knows?

Musashi

2005-Sep-29, 04:27 PM

That is not quite true. For instance, one could have three territories side by side. The graph would have three circles in a row, joined by just two lines.

I have a feeling that that is not going to make a difference in your proof, but who knows?

Don't all the territories need to be connected to each other? In that case, the three side by side would be connected by two lines PLUS another line connectin the outer two territories together.

http://img307.imageshack.us/img307/8245/threev8qc.gif (http://imageshack.us)

For the next step, it doesn't seem to matter where you put the 4th, it is going to isolate (at least) one of the other territories from a future 5th. This is the big step, I imagine, figuring out how to place a 4th so that it doesn't isolate. I haven't been able to do it, and even though I have only been trying since last night, it is not apparent to me that it is even possible.

http://img263.imageshack.us/img263/3024/fourv7ob.gif (http://imageshack.us)

Grey

2005-Sep-29, 05:26 PM

Don't all the territories need to be connected to each other? In that case, the three side by side would be connected by two lines PLUS another line connectin the outer two territories together.I don't think there's any specific requirement that all the territories touch each other, the arrangement Pace suggests is certainly possible. However, it's also true that, since we're trying to establish the maximum number of regions that could in principle be touching, it's pretty likely that simply choosing not to have two regions be adjacent when they could be isn't going to get you far.

For the next step, it doesn't seem to matter where you put the 4th, it is going to isolate (at least) one of the other territories from a future 5th. This is the big step, I imagine, figuring out how to place a 4th so that it doesn't isolate. I haven't been able to do it, and even though I have only been trying since last night, it is not apparent to me that it is even possible.If it were possible, that would of course be a counterexample to the four color theorem. I think, actually, that it's fairly easy to show that no arrangement of just five territories can have all of them touching each other. I think that most of those who think the four color theorem is false (I think there are pretty few such people, actually) think that there might be an arrangement of more than five territories which somehow forces at least five to all be touching each other.

The use of pictures is nice. Maddad, may I recommend doing the same? It will probably save you some time explaining what you mean, and making sure that we're all drawing the same pictures as we follow along at home. :)

hhEb09'1

2005-Sep-29, 05:26 PM

Don't all the territories need to be connected to each other? In that case, the three side by side would be connected by two lines PLUS another line connectin the outer two territories together.It's certainly not true in real life--Virginia, North Caroliina, and South Carolina, USAn states, are connected, but Virginia does not share a border with South Carolina. As I said, it may not make a difference in the proof, but it is not true that all three have to touch the other two, even if they are all connected.

For the next step, it doesn't seem to matter where you put the 4th, it is going to isolate (at least) one of the other territories from a future 5th. This is the big step, I imagine, figuring out how to place a 4th so that it doesn't isolate. I haven't been able to do it, and even though I have only been trying since last night, it is not apparent to me that it is even possible.It's not possible. Or, as peter eldergill said, a complete graph on five points cannot be planar.]

Musashi

2005-Sep-29, 05:36 PM

Well, I am trying to be openminded about Maddad's claim. I hope he comes back and tells me where to put #4 so that I can still place #5 properly.

As far as real life, from what I know, the four color theorem doesn't really have anything to do with real life maps. I also don't see how adding verticies that don't connect to the others helps disprove the theorem (and keep it simple). Would you mind explaining?

Grey

2005-Sep-29, 05:55 PM

Well, I am trying to be openminded about Maddad's claim. I hope he comes back and tells me where to put #4 so that I can still place #5 properly.No, Maddad still thinks the four color theorem is true. He just thinks that a proof using a computer is not a valid proof, and says that he has a simpler one.

By the way, I'm wrong about this:

I think that most of those who think the four color theorem is false (I think there are pretty few such people, actually) think that there might be an arrangement of more than five territories which somehow forces at least five to all be touching each other.A bit of quick reading shows that it's pretty easy to prove that you can't get five regions to all be bordering each other at the same time. However, that by itself doesn't prove the four color theorem. Why not? Well, the largest number of regions that a territory touches isn't necessarily the same as the number of colors needed for the map. For example, a ring of five regions (like the one on the left here (http://www.mathpages.com/home/kmath266/Image4247.gif)) has no region touching more than two other regions, yet it requires three colors.

Musashi

2005-Sep-29, 06:28 PM

Ah! That is what I get for reading the first half and the second half of this thread at different times. Sorry. Things are a bit clearer now. Thank you Grey.

hhEb09'1

2005-Sep-29, 06:28 PM

I also don't see how adding verticies that don't connect to the others helps disprove the theorem (and keep it simple). Would you mind explaining?As Grey points out, and others have said, there is no set of five regions where all five touch each of the other four. That's easy to show. Over a hundred years ago, it was shown that even a map of a few dozen territories was insufficient to force five colors--but obviously, there are territories that don't touch each other in that map. Eventually, you do have to add territories that don't touch each other, in producing such maps.

But, as I say, I don't think that is going to make much difference in this proof.

worzel

2005-Sep-29, 06:50 PM

As I said, it may not make a difference in the proof, but it is not true that all three have to touch the other two, even if they are all connected.But we already know that we may as well only consider maximal planar graphs, because if they are four-colorable, then trivially so are non-maximal ones. I'm having difficulty seeing how non-maximal ones could be crucial to any proof. But then you could say that we also know from Kempe that we might as well start with a vertex with five edges, and assume that the rest of the map is four-colorable, but this is Maddad's proof, so we should stay open minded as you say, and see where he's going. Let's hope this one doesn't take 10 years to disprove :)

Grey

2005-Sep-29, 10:41 PM

But we already know that we may as well only consider maximal planar graphs, because if they are four-colorable, then trivially so are non-maximal ones. I'm having difficulty seeing how non-maximal ones could be crucial to any proof.I don't want to try to speculate much further until we see the next step from Maddad, but there is at least one thing to consider here. It's true that we need only consider maximally connected graphs, but if we're building up the graphs by adding one vertex at a time and then establishing all legitimate connections, I think that doesn't span the space of all maximally connected graphs. That is, I'm fairly certain that there exist maximal graphs for which the removal of any single vertex will leave you a non-maximal graph, and if you were to add all possible connections to this smaller graph (to make it maximally connected), you could no longer create the original graph by the re-addition of a vertex. So a proof that builds up a graph by the addition of vertices one at a time will at least need to allow non-maximal graphs in the construction process. Does that make sense? Can someone who has done more work in graph theory confirm or deny this?

Maddad

2005-Sep-29, 11:10 PM

Maddad, have you studied graph theory? . . . I'm not sure where you're going with this yetHaven't studied it yet, but I get into stuff like that as it crosses what I need. Where I'm going is to construct a diagram representative of any possible arrangement of four territories that allows you to see at a glance that you are unable to add a fifth territory in such a way that it borders all four other territories.

That is not quite true. For instance, one could have three territories side by side. The graph would have three circles in a row, joined by just two lines.It is indeed quite true. Those three territories must all border the other two, so the side of the two outside ones must flow above or below the center one to meet up. After thinning the flow to lines, this becomes exactly the equallateral triangle described in my longer previous post.

Musashi is now on the right track. Thank you very much for the drawings, by the way. Yes, the territories do need to be all connected to each other. You have reduced the territories to black dots, but that works just fine. I'll run with this representation.

"For the next step, it doesn't seem to matter where you put the 4th, it is going to isolate (at least) one of the other territories from a future 5th." Bingo! You got it. You skipped though one possibility. That fourth territory could be added outside the diagram instead of inside it. How about making us one more drawing of a three territory triangle with the fourth territory added outside the diagram? I would appreciate that very much.

"This is the big step, I imagine, figuring out how to place a 4th so that it doesn't isolate. I haven't been able to do it, and even though I have only been trying since last night, it is not apparent to me that it is even possible." You're right on both counts. It's a big step, and it's not possible. In being not possible, it proves the Four Color Map Theorem. However, before we claim solution, we need to see how adding the fourth territory outside the triangle of three territories relates to the diagram of four territories you have already given us. You will see that they are actually identical.

Thank you again Musashi. You've saved me a ton of explanation that I was dreading.

worzel

2005-Sep-29, 11:16 PM

Does that make sense? Yes, good point Grey, I think I've found an example of what you're talking about (see attachment). We have to start with a triangle (say abc), then when we must add another vertex (say d) such that it has an edge with a,b, and c. But there is no vertex in the example that has an edge to each vertex of a triangle.

Sorry if I'm sidetracking the discussion a bit, Maddad, maybe you can help us get back on track and add the fourth vertex.

worzel

2005-Sep-29, 11:29 PM

You're right on both counts. It's a big step, and it's not possible. In being not possible, it proves the Four Color Map Theorem.This sounds like you're saying that proving the theorem involves only proving that you can't draw five territories such that they all touch each each other. Is that the case, or am I just being impatient?

Musashi

2005-Sep-30, 12:51 AM

You skipped though one possibility. That fourth territory could be added outside the diagram instead of inside it. How about making us one more drawing of a three territory triangle with the fourth territory added outside the diagram? I would appreciate that very much.

I am not sure what you mean by outside the diagram. In both of the 4 territory maps, I added the 4th above the sets of three and then connected. Here I will do it again starting with two triangles and putting one 4th in the center (bottom picture) and one below the triangle (top picture).

http://img121.imageshack.us/img121/7245/fourvii6oa.gif (http://imageshack.us)

I am pretty sure that no matter where I put the 4th, as long as it is outside the triangle, it will isolate one territory.

peter eldergill

2005-Sep-30, 02:49 AM

"For the next step, it doesn't seem to matter where you put the 4th, it is going to isolate (at least) one of the other territories from a future 5th." Bingo! You got it. You skipped though one possibility. That fourth territory could be added outside the diagram instead of inside it. How about making us one more drawing of a three territory triangle with the fourth territory added outside the diagram? I would appreciate that very much.

"This is the big step, I imagine, figuring out how to place a 4th so that it doesn't isolate. I haven't been able to do it, and even though I have only been trying since last night, it is not apparent to me that it is even possible." You're right on both counts. It's a big step, and it's not possible. In being not possible, it proves the Four Color Map Theorem. However, before we claim solution, we need to see how adding the fourth territory outside the triangle of three territories relates to the diagram of four territories you have already given us. You will see that they are actually identical.

.

Sounds to me that you've proved that K5 is not planar, which I'm pretty sure doesn't prove the four colour theorem

Pete

ZaphodBeeblebrox

2005-Sep-30, 04:14 AM

Sounds to me that you've proved that K5 is not planar, which I'm pretty sure doesn't prove the four colour theorem

Pete

Isn't that, The Point, though?

Maps, are Two-Dimensional!!!

QED

worzel

2005-Sep-30, 11:53 AM

Isn't that, The Point, though?

Maps, are Two-Dimensional!!!

QEDNo, it's not enough. Here's a map that has no set of 4 mutually connected vertices (doesn't contain k4).

http://mboyd.demon.co.uk/fct-pent.jpg

Yet it requires at least four colors. We need at least three for b,c,d,e,f, because with only two we must alternate and will end up with two bordering with the same color. a must be different to all b,c,d,e,f so it must use a fourth color.

So we have a map that requires four colors even though it doesn't contain k4. How do we know that there aren't similar maps that require 5 colors even though they don't (and inded can't) contain k5?

peter eldergill

2005-Sep-30, 05:18 PM

This is from Wikipedia, with references and all

http://en.wikipedia.org/wiki/Four_color_theorem

Apparantly, The Four Colour Theorem stated in graph theory terms is very simple:

Prove that any planar graph is four colourable (colourable meaning adjacent vertices have different colours)

There is also (an outline of) a proof of the five colour theorem at

http://en.wikipedia.org/wiki/Five_color_theorem

Pete

hhEb09'1

2005-Sep-30, 07:44 PM

It is indeed quite true. Those three territories must all border the other two, so the side of the two outside ones must flow above or below the center one to meet up. After thinning the flow to lines, this becomes exactly the equallateral triangle described in my longer previous post.It may be true in your proof, sure, but my point was just that in general it is not true.

So a proof that builds up a graph by the addition of vertices one at a time will at least need to allow non-maximal graphs in the construction process. Does that make sense? Can someone who has done more work in graph theory confirm or deny this?Yes, that was my point. But it's clear now that it does not make a difference, in this proof.

It's a big step, and it's not possible. In being not possible, it proves the Four Color Map Theorem.That's the wrong Four Color Map Theorem. :)

Grey

2005-Sep-30, 09:06 PM

Yes, good point Grey, I think I've found an example of what you're talking about (see attachment).Yes, I think that's the smallest possible graph that serves as an example. It's maximally connected, but removing any vertex gives a graph which is not.

Sounds to me that you've proved that K5 is not planar, which I'm pretty sure doesn't prove the four colour theorem.You're correct, Peter. That wasn't actually clear to me when this discussion started, but worzel has stated the simplest objection. DeMorgan was able to show that five regions cannot be in contact with each other in 1852, when he was first introduced to the question, but also realized that this doesn't settle the question of whether four colors is always sufficient to color any map.

Here (http://www.mathpages.com/home/kmath266/kmath266.htm) is a site that I found very useful in discussing the history of the four color theorem, discussing some of the subtleties (like this one) involved in proving it, describing the simpler proofs that six or five colors are sufficient (showing that six is sufficient is almost trivial), and giving the general outline of the proof given by Appel and Haken.

worzel

2005-Oct-01, 10:08 AM

Great link, Grey. Here's (http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm) a very accessible one I found that explains Kempe's proof, and the flaw in in it.

01101001

2005-Oct-01, 11:01 PM

Where's the rest of Maddad's proof of the Four Color Theorem? How does it proceed from 4- and fewer-node planar graphs being at most four-colorable to all planar graphs?

Maddad

2005-Oct-02, 01:13 AM

This sounds like you're saying that proving the theorem involves only proving that you can't draw five territories such that they all touch each each other. Is that the case, or am I just being impatient?Bingo. Remember, we are now satisfied that the triangle is representative of every possible arrangement of three territories. (I understand that we have one holdout, hhEb09'1's, who rejected my answer to his objection.) Since the triangle represents every possible arrangement of three territories, identifying every possible place that the fourth territory may go would mean we can be confident of diagramming every possible arrangement of four territories. Our objective to prove the theorem is to show what the maximum number of territories will be. We will find that at four because we will be unable to add the fifth territory.

I am pretty sure that no matter where I put the 4th, as long as it is outside the triangle, it will isolate one territory.Yes, when you draw the fourth territory outside the triangle as you have done in placing it underneath, the loop around the left side isolates the left side territory from a fifth outside territory placement in the resulting diagram of four territories. In fact, wherever you place your new territory, the loop to connect it to the last territory will isolate one territory from a new fith outside territory. I does not though cover internal palcement in a four territory map, which we will deal with next. Before it gets too confusing though, we are going to show that those last two diagrams you drew are actually identical.

Isn't that, The Point, though? Maps, are Two-Dimensional!!!

QEDFor the purposes of this proof, yes they are because I have defined them that way. They are not only two dimensional, they are also limited rather than endless. Once we have a clear grasp of the logic behind working the theorem, then it will be an easy matter to extend our definition to an unlimited two dimensional surface or a curved surface.

Yet it requires at least four colors. We need at least three for b,c,d,e,f, because with only two we must alternate and will end up with two bordering with the same color.Actually, your map requires only three colors. Note that territory abc may be the same color as ade, and territory acd may be the same color as aef.

Maddad

2005-Oct-02, 01:31 AM

Ok, we are going to take another look at the two seemingly different drawings that Musashi provided for us. Rember how we bent the bars of the three territories in a row to match the initial three territories arranged in an equallateral triangle? We're going to do the same thing to morph Musashi's two diagrams in his last image until they match each other. We'll leave the bottom one alone to use as a reference for what we want the upper one to become.

First we shorten the center bar, pulling the three territories on the left into a vertical line. The loop on the left is now a bit longer than we need, so we'll just tug on it to shorten it up a bit for neatness's sake. Now we'll scoot the territory on the right and the on in the center downward. We stop when we readch 60 degree angles with the various territories. After pulling the looping connecting borders to a straight line, we should be able to wind up with a diagram that looks just like Musashi's bottom diagram of four territories. This means that every possible arrangement of four territories may be faithfully represented on this map by his bottom image.

Since we now have a single diagram for four territories, all that is left to do is examine where we can add the fifth territory. There are only two possible locations, similar to the two possible locations in the thee territory diagram. We may add the fifth territory to the exterior of the diagram, or we may add it to one of the three identical interior cells. By now some of you can see what is about to happen.

hhEb09'1

2005-Oct-02, 06:57 AM

Actually, your map requires only three colors. Note that territory abc may be the same color as ade, and territory acd may be the same color as aef.The territories are a and b and c and d and e and f. The borders are the lines between them.

worzel

2005-Oct-02, 08:48 AM

This sounds like you're saying that proving the theorem involves only proving that you can't draw five territories such that they all touch each each other. Is that the case, or am I just being impatient?Bingo. Remember, we are now satisfied that the triangle is representative of every possible arrangement of three territories. (I understand that we have one holdout, hhEb09'1's, who rejected my answer to his objection.)Only if the graph is required to be maximally connected. But as Grey pointed out, you can't reach all maximally connected graphs adding one vertex at a time such that each graph along the way is also maximally connected (if you could, the four color theorem is actually quite easy to prove). But when you said, "Those three territories must all border the other two, so the side of the two outside ones must flow above or below the center one to meet up," it sounds like you're arguing from the point of view that a map must completely cover the plane. As hhEb09'1 has said, that may be a requirement of your proof but it is not a requirement of planar maps in general. Moreover, even if that is a requirement of your proof, you are still wrong. Here's a map (an actual map, not a graph) of three territories covering the plane that do not all touch each other. Under it is the graph representing this map which is also the graph hhEb09'1 pointed out to you.

http://mboyd.demon.co.uk/fct-three.gif

None of this is probably relevant to your proof though. How about assuming for the sake of argument that we all understand and agree that one cannot create a map with five mutually bordering regions. How do you get from there to proving the four colour theorem?

mickal555

2005-Oct-02, 11:47 AM

Hmmm, I tried to disprove it in pait- just for fun...

Remarkable how it works....

hhEb09'1

2005-Oct-02, 02:11 PM

Under it is the graph representing this map which is also the graph hhEb09'1 pointed out to you.Thanks worzel, that's a good example map, since it leaves no "room" to create an arbitrary path from a to c.

Maddad

2005-Oct-03, 01:33 AM

The territories are a and b and c and d and e and f. The borders are the lines between them.Hmmm. You still need only four colors. Territory b borders territories f, a, and c which allows you to color c and d the same way you do b. While it does require four colors, it does not show that you cannot arrange five territories in such a way that each one touches all the other four in a line or arc segment. Therefore it does not prove the Theorem.

Only if the graph is required to be maximally connected. But as Grey pointed out, you can't reach all maximally connected graphs adding one vertex at a time such that each graph along the way is also maximally connectedThe term maximally has not been definied. I can indeed satisfactorily connect the territories because I have.

when you said, "Those three territories must all border the other two, so the side of the two outside ones must flow above or below the center one to meet up," it sounds like you're arguing from the point of view that a map must completely cover the plane.I defined the plane as limited. The territories must indeed meet up because we are examining the maximum number of territories that do meet up.

The reason your map of A, B, and C is not relevant for the discussion is because A is isolated from C. No territories may be isolated from any other if you are to proceed.

worzel

2005-Oct-03, 09:20 AM

Hmmm. You still need only four colors. Territory b borders territories f, a, and c which allows you to color c and d the same way you do b. While it does require four colors, it does not show that you cannot arrange five territories in such a way that each one touches all the other four in a line or arc segment. Therefore it does not prove the Theorem.The only purpose in presenting that graph was as an example of a maximally connected graph that can not be constructed one vertex at a time such that each graph thus obtained is also maximally connected.

The term maximally has not been definied. We're all using the standard definition: a maximal planar graph is one where no more edges can be added (assuming only one edge is allowed per pair of vertices). Equivalently, every face of a maximal planar graph is a triangle.

I can indeed satisfactorily connect the territories because I have.Indeed you can, but you claimed that your triangle was the only graph possible for three territories, that was incorrect.

I defined the plane as limited. The territories must indeed meet up because we are examining the maximum number of territories that do meet up.The problem here is that if you're only going to consider graphs that result from you making the maximum number of connections possible each time you add a vertex then your proof won't apply to the graph you referred to above because it can't be constructed that way.

The reason your map of A, B, and C is not relevant for the discussion is because A is isolated from C. No territories may be isolated from any other if you are to proceed.It's only relevance was to show that your statement that your triangle was the only possible graph representing three territories was incorrect. If you require that your graphs be maximally connected then that example is not relevant, but then you can't construct the previous example :) If you require that every territory added must border every other territory then you can't get past four territories so your proof is limited to maps with only four regions.

Of course, none of us can tell if any of these points are relevant to your proof because you haven't finished presenting it yet. So rather than you requiring us to all agree on each step you take and every word you say before moving onto the next one, and us therefore being bound to go over every proviso due to your lack of rigour, why not just present the rest of your proof. Then we can either congratulate you or focus on just the bit where you went wrong.

Maddad

2005-Oct-03, 08:37 PM

you claimed that your triangle was the only graph possible for three territories, that was incorrect.Not quite. I claimed the triangle was representative of every possible way to satisfactorily arrange three territories, which is different. I said nothing about where there could be another way to represent them.

It's only relevance was to show that your statement that your triangle was the only possible graph representing three territoriesAs in the quote above, you are reading something into my statements that is not there. While it is a graph of every possible arrangement, it is not the only possible graph, which is different.

then you can't construct the previous exampleI can't tell you how impressed I am that you think I cannot do what I have done. If I ever need someone to explain something, I'll be sure to come looking for you.

rather than you requiring us to all agree on each stepIf you cannot understand the current step, then you cannot understand the next since each step is built upon the previous one. Since you want to argue, instead of seeing the solution, I have no interest in progressing with you.

worzel

2005-Oct-03, 10:22 PM

Not quite. I claimed the triangle was representative of every possible way to satisfactorily arrange three territories, which is different. I said nothing about where there could be another way to represent them.Well you never defined "satisfactorily", maybe you should, it is certainly not representative of every three territory map. But you've got it the wrong way round anyway. This map

http://mboyd.demon.co.uk/fct-three.gif

is a map who's graph is not a triangle, its graph below it is not another way to represent your triangle graph.

As in the quote above, you are reading something into my statements that is not there. While it is a graph of every possible arrangement, it is not the only possible graph, which is different.Again, you have it the wrong way round. No one is saying that there are other ways to represent what your graph represents. What we are saying is that your graph does not represent every possible three territory map. If you are placing restrictions on the construction such that your triangle is representative of every possible restricted construction then you need to be explicit about those restrictions so that we can evaluate whether or not your proof covers all maps.

then you can't construct the previous exampleI can't tell you how impressed I am that you think I cannot do what I have done. If I ever need someone to explain something, I'll be sure to come looking for you.Thank you for cutting the qualification out of that sentence. In case you misunderstood I'll try to rephrase it for you: If you require that every map in your construction as you iteratively add vertices be fully connected then you can not construct this map:

http://mboyd.demon.co.uk/fct-diamond.gif

If that is your requirement and you don't agree, show us how you can construct the above map one vertex at a tine while maintaining a fully connected graph at each stage. If that is not your requirement, then tell us what your requirement is (there must be one, since you disallow my map above) and move on from this then irrelevant point.

If you cannot understand the current step, then you cannot understand the next since each step is built upon the previous one. Since you want to argue, instead of seeing the solution, I have no interest in progressing with you.I am sorry you feel that way. I do not want to argue for its own sake, but if you require that I agree to every step along the way then I must point out where I don't agree. Otherwise, if the last step is valid, but a previous step that I had agreed to for the sake of argument is not, then I have no choice but to back up and contradict myself by disagreeing with a step that I previously agreed with. It is quite likely, however, that these points may be moot. We can not know until you actually provide your proof. So rather than waste time arguing the toss over points that may well turn out to have no impact on your proof, why don't you just get on with it.

If you take exception to me (sorry guys, I never was any good with rope) then just ignore me for now and get on with it anyway for the benefit of all those eager, and rather patient, observers who are still with us.

Grey

2005-Oct-04, 01:38 AM

Maddad, these are indeed side issues, and perhaps we shouldn't have brought them up while waiting for your next step. But worzel is correct, in that by presenting each step one at a time, it becomes necessary to raise any issues with that step, even if those issues do not have any actual bearing on the proof.

But perhaps we can cut to the chase, as it were. Even though you haven't quite completed your proof, from your comments you seem to be under the impression that merely showing that five territories cannot mutually touch each other is sufficient to prove the Four Color Theorem. Am I correct in that?

peter eldergill

2005-Oct-04, 02:04 AM

Yes, Maddad, I think that also. Your posts are getting very defensive , especially when you say things like

Since you want to argue, instead of seeing the solution, I have no interest in progressing with you.

You made no mention of the sites I suggested and since you're trying to use Graph Theory to prove your result, I think it would be good to at least learn a couple of the terms, and perhaps even go through the prrof of the five colour theorem to get some good ideas.

This sarcasm is also not warranted, in my opinion:

I can't tell you how impressed I am that you think I cannot do what I have done. If I ever need someone to explain something, I'll be sure to come looking for you.

You've spent most of your posts talking about moving territories around. The location of the territories is not relevant, only the colour of the vertex. In graph theory, the only thing that defines an edge is the end vertices, not the distance, placement of veritces, shape of the edge, etc.

Later

Pete

Maddad

2005-Oct-05, 11:46 PM

worzel is correct, in that by presenting each step one at a time, it becomes necessary to raise any issues with that step, even if those issues do not have any actual bearing on the proof.Not quite. If it does not bear on the proof, then it is just a distraction.

you seem to be under the impression that merely showing that five territories cannot mutually touch each other is sufficient to prove the Four Color Theorem. Am I correct in that?Provided that you can show that the diagram represents every possible way of arranging the territories in the universe you have defined, then yes, it proves the theorem.

worzel

2005-Oct-06, 12:02 AM

you seem to be under the impression that merely showing that five territories cannot mutually touch each other is sufficient to prove the Four Color Theorem. Am I correct in that?

Provided that you can show that the diagram represents every possible way of arranging the territories in the universe you have defined, then yes, it proves the theorem.How have you defined your universe of territories? Is is that no territory may be added unless it connects to every other territory already added? You seemed to say so when you said "No territories may be isolated from any other if you are to proceed."

hhEb09'1

2005-Oct-06, 09:57 AM

worzel is correct, in that by presenting each step one at a time, it becomes necessary to raise any issues with that step, even if those issues do not have any actual bearing on the proof.Not quite. If it does not bear on the proof, then it is just a distraction.If it does not bear on the proof, why make the comments that raise the issues? They're distracting :)

Grey

2005-Oct-06, 12:50 PM

Not quite. If it does not bear on the proof, then it is just a distraction.The point was that you weren't presenting your entire proof, just each individual step, so we therefore didn't know what would be relevant to the proof and what would not.

Provided that you can show that the diagram represents every possible way of arranging the territories in the universe you have defined, then yes, it proves the theorem.Ah, well that answers that issue then. DeMorgan realized back in 1852 when he was originally presented with the question that it was impossible to have five regions that mutually touch each other, so your proof is actually nothing new. Unfortunately, it's also not sufficient to prove the Four Color Theorem (which DeMorgan also realized). It might be possible for a single territory to touch four others, which, because of their connections to other various territories, are forced to have four different colors, and hence the territory in question would have to use a fifth one. Now, this may not be possible (indeed, if one accepts the standard proof, it is not), but you haven't shown that.

Look again at worzel's example. I'll redraw it so that it's clear what the territories are, just in case that was a concern (we'll see if I can get the upload files feature to work here). Remember, the dots are the territories, the lines show which ones border which others, which is the standard convention you were using as well. If it's confusing, I can always draw the actual map that corresponds to this graph. Anyway, this is a map which has no set of mutually touching territories larger than three, yet it requires four colors. So we can see immediately that the number of colors required for a map is not necessarily the same as the largest number of territories that touch each other.

Maddad

2005-Oct-06, 03:56 PM

The point was that you weren't presenting your entire proof, just each individual step, so we therefore didn't know what would be relevant to the proof and what would not.I can see your point.

DeMorgan realized back in 1852 when he was originally presented with the question that it was impossible to have five regions that mutually touch each other, so your proof is actually nothing new.The question the theorem tries to settle is why each of the five regions are unable to touch all the other four. Knowing that they cannot wasn't ever an issue.

It might be possible for a single territory to touch four others, which, because of their connections to other various territories, are forced to have four different colors, and hence the territory in question would have to use a fifth one. Now, this may not be possible (indeed, if one accepts the standard proof, it is not), but you haven't shown that.Being forced to use a different color is a result of touching another territory. If they do not touch, then you may use the color of that territory. If they do touch, then you must use another.

I allowed myself to get derailed by irrelevant comments a few days ago. The conclusion of the proof is that since the diagram of four territories, a triangle with the fourth in the center, has only two possible places for the fifth territory, you only have to show that neither choice allows a connection to all four previous territories. If you choose external placement, then you are isolated from the center territory. If you choose one of the three identical internal cells, then you are isolated from the territory at the far corner.

I do not need to look at worzel's example. I am perfectly willing to admit that he is unable to solve the theorem with his approach.

pghnative

2005-Oct-06, 04:15 PM

The question the theorem tries to settle is why each of the five regions are unable to touch all the other four.

From my reading of this thread, that is not what the theorem is trying to settle.

It might be possible for a single territory to touch four others, which, because of their connections to other various territories, are forced to have four different colors, and hence the territory in question would have to use a fifth one. Now, this may not be possible (indeed, if one accepts the standard proof, it is not), but you haven't shown that.

Being forced to use a different color is a result of touching another territory. If they do not touch, then you may use the color of that territory. If they do touch, then you must use another.Incorrect. See worzels example above where no territory touches more than two other territories. By your logic only three colors should be needed. But in the example, four colors must be used. This seems to be the critical point that you are missing.

editted three times due to my incompetance with nested quotes

peter eldergill

2005-Oct-06, 04:22 PM

It's not Worzel who's trying to solve the problem, it's you...and yes, you are claiming that since K5 is not planar, then the 4 colour theorem is proved.

As mentioned by Grey, this is not sufficent.

The question the theorem tries to settle is why each of the five regions are unable to touch all the other four. Knowing that they cannot wasn't ever an issue.

It is precicesly the issue, as you are using it to try to prove your theorem.

I do not need to look at worzel's example. I am perfectly willing to admit that he is unable to solve the theorem with his approach.

Wow...ignoring counterexamples or other cases which can possibly show your proof is incorrect, or needs revising. Is that really how you think mathematics should be? Calling our comments "irrelevant" is not particularly polite, either, and won't convince me that your proof is valid.

Pete

hhEb09'1

2005-Oct-06, 05:16 PM

(color added)

The conclusion of the proof is that since the diagram of four territories, a triangle with the fourth in the center, has only two possible places for the fifth territory, you only have to show that neither choice allows a connection to all four previous territories. If you choose external placement, then you are isolated from the center territory. If you choose one of the three identical internal cells, then you are isolated from the territory at the far corner.That does not prove the Four Color Map theorem, as has been said, but I'm curious about what the tattoo would have looked like.

01101001

2005-Oct-06, 05:28 PM

Invalid. Nice try.

worzel

2005-Oct-07, 12:13 AM

OK Maddad, I'm going to ignore your scathing comments and resist the urge to quote every instance where you claimed my comments were irrelevant, followed by every instance of someone referring to my posts in attempting to convince you that your proof is mistaken (although I couldn't resist making this irrelevant point :)).

By now it is clear to everyone that your proof is wrong, and that the provisos we were discussing were actually quite relevant. All we have left to do is to hopefully convince you that you are wrong. Maybe this will spur you on to investigate further. I, personally, would love to see a simple proof of the FCT - I've had a go at it a few times myself but have never really got anywhere (it's one of those nagging problems that just ought to have a simple proof).

I was quite impressed, by the way, that you figured out that representing territories and borders with graphs was the way to go. I never thought of that before I first read it somewhere (although I probably read it a few pages after first reading about the FCT). You shouldn't take it personally when we criticise your proof - that is how all scientific and mathematical ideas are tested: can they stand up to criticism - not that this is a peer reviewed journal, but it's better than nothing (and there are some frighteningly smart people here).

Right. Take the map of the United States (or something similar). Suppose that we have colored it using only four colors. Now suppose we add the sea and for some strange reason we decide that we should use one of the colors already used. But when we do we find that each of the four colors is already used on at least one coastal state. What can we do? Well we could try changing the color of all the blue coastal ones, say, to free up blue for the sea. But in doing so, what if we find that some of these blue ones border three differently coloured states? After changing a blue coastal state like this we will need to recolor one of its neighbours also. But what if we encounter the same problem with the neighbour we recolor? Well we could just keep on recoloring and see what happens. But what if we end up back on the coast again but this time we find ourselves left with no choice but to color a coastal state that wasn't blue and the only choice we have left is blue due to the recoloring choices we made earlier?* Maybe we could backtrack and try out some different choices. The four color theorem basically says that if we do backtrack eventually we will find a set of choices that will allow us to color the states and the sea using only four colors - but it may be quite difficult to figure out what those choices are.

I hope that you can see that this is far more complex and subtle than simply showing that five states can't all border each other.

*If we make the decision never to choice another coastal state for recoloring after our initial one, how do we know that this process will ever end?

Grey

2005-Oct-07, 01:29 PM

The question the theorem tries to settle is why each of the five regions are unable to touch all the other four. Knowing that they cannot wasn't ever an issue.I see at least two misconceptions here. The first is simply that whether it's possible to have five mutually touching regions in a graph is not the question addressed by the four color theorem. The question is whether it's possible to draw a graph that would require more than four colors to make certain that all adjacent regions are colored differently. To be sure, they are closely related questions, and if it were possible for five regions to touch each other, that would certainly mean that the four color theorem was false. However, the reverse is not true; showing that five regions cannot touch is not sufficient to prove the four color theorem. More about that below.

The second problem here, though, is that a proof in mathematics is never about showing why something is true, when that something was already known to be true. If we know something is true, it's because we have a proof demonstrating that. If we don't have a proof, then we cannot be sure that it's true. DeMorgan knew that it's not possible for five regions to be in mutual contact not because it was obvious, or because nobody was able to come up with a counterexample, but because he was able to demonstrate it, using a proof essentially equivalent to yours.

Being forced to use a different color is a result of touching another territory. If they do not touch, then you may use the color of that territory. If they do touch, then you must use another.True, but remember that regions need not be in direct contact in order to constrain what colors can be used for them. That is, the color of a region directly constrains the colors of regions it borders. Those regions may then constrain colors of regions that border them, and so forth, which means that the choice of color for the first region may have an indirect effect on the available colors for those other regions, even though it does not directly border them. Thus, it may be necessary to consider regions beyond those that immediately border any one region to determine the number of colors required for a map. For example, I've added an outside region to the one worzel used (note that this also makes it a maximally connected graph, just in case that was an issue for some reason). Now, if you start by choosing a color for the central region, the outer region will always end up the same color, no matter what choices you make for all the other regions.

I allowed myself to get derailed by irrelevant comments a few days ago. The conclusion of the proof is that since the diagram of four territories, a triangle with the fourth in the center, has only two possible places for the fifth territory, you only have to show that neither choice allows a connection to all four previous territories. If you choose external placement, then you are isolated from the center territory. If you choose one of the three identical internal cells, then you are isolated from the territory at the far corner.No trouble here. I think we'll all accept that four mutually touching regions is the most possible in a map.

I do not need to look at worzel's example. I am perfectly willing to admit that he is unable to solve the theorem with his approach.He's not trying to prove the four color theorem, he's showing where you've made an unfounded assumption. Let me try to make this explicit. You're saying, "no more than four regions can mutually touch each other in a two dimensional map, therefore no more than four colors are need to color any map such that no two adjacent territories have the same color". You should be able to see that there is an assumption being made here. Namely, that the largest number of regions in mutual contact is the same as the number of colors required for the map. However, if you look carefully at the graph (you can find an example that works in this message as well, if you don't want to go back to worzel's post), you'll see that there is no group of regions in mutual contact larger than three. Let me repeat that: there is no place in this graph where you have four regions touching each other. However, this map requires four colors to paint, not three. Therefore, it is not true that the number of regions in largest group which all border each other in a map is also the same as the minimum number of colors for that map. Without that additional assumption, you cannot get from what you've shown (which you've done quite nicely) to what the four color theorem states.

Maddad

2005-Oct-07, 07:31 PM

I will address one single and especially idiotic statement out of a choice of many. That by pghnative is particularly enlightening because it speaks to the core of our discussion:

"Originally Posted by Maddad

The question the theorem tries to settle is why each of the five regions are unable to touch all the other four. [Knowing that they cannot wasn't ever an issue.]"

From my reading of this thread, that is not what the theorem is trying to settle.Incorrect.Thirty five years ago I picked up the Life Science Library book on Mathematics, copyrighted in 1963 and again in 1969. It presents the Four Color Map Theorem on pages 184 and 185. Since I still have that book in one of my living room bookcases, let me quote you what David Bergamini and the editors of Time said about your post: "no one has been able to prove what map makers have known for ages—that four colors are enough for any flat map or sphere."

Got that pghnative?

Look, I cannot believe that you guys are really that stupid. You are not; you are probably reasonably intelligent. So what is the problem? Why are you having so much trouble understanding such a simple idea? The answer is that you feel threatened by me. I am asking you to think, and thinking of a new idea is difficult.

One of the members here labeled someone an expert because they had supposedly come up with a proof. Never mind that nobody here can understand that proof. Never mind that we know of nobody who has verified it. Never mind that experts have been known to make mistakes. Never mind that the member making this interesting statement does not really know what qualifications this expert has to earn the title of expert. (Yes, I know you can know go look it up now, but you did not know when you were certain this man was the last word on the subject.) We have called them an expert, and from that concluded that the issue is settled and therefore needs no further investigation. What you are doing is insulating yourself from a need to think. Once you call him an expert, you need think no further.

Pghnative, why in God’s name do you want me to examine worzel’s example? I have not even bothered reading his last post. A month ago he jumped into this thread without a clue; look at his first two posts. He still does not get it; look at his last post. Yes, he is dealing with diagrams that are distantly related to mine because they are colored territories, and some of them do border others. If he though, like you, cannot understand the very most fundamental statement of the Four Color Map Theorem given in red above, then what possible hope does he have of contributing anything useful? Why should I waste my time chasing someone else’s approach to arranging territories when it does not bear on the method I am using to limit possibilities to manageability? I developed this approach specifically to deal with this problem. Saying that my approach is different from what worzel heard about is expected. I solved the problem; worzel and company did not. If it bears a resemblance to something worzel’s heard about, then that does not mean that it must share all characteristics with mine. In fact, it should not, because if it did, everybody here would still not understand why we do not need more than four colors to draw a map.

As I had said I would, I have provided the proof of the Four Color Map Theorem. You may accept it or reject it, as you choose. It is not my job to drag you by the scruff of your collective necks to make you think. Thinking is a privilege and an art, but it is not easy. If you are more secure in finding excuses not to think, then by all means, do so. I am done with this thread and will not return to it to read any further comments.

hhEb09'1

2005-Oct-07, 07:49 PM

As I had said I would, I have provided the proof of the Four Color Map Theorem.D*ng. But at least, my hat (http://www.bautforum.com/showpost.php?p=558098&postcount=39) is safe this time. :)

PS: This is part of the maddingly attractive nature of the four color map theorem--it seems like it should be so easy to apply it to a map of any number of territories, once you have shown it for a map with just five. Some of the world's greatest mathematicians have tried and failed to extend it past the point that Maddad achieved. Some of them convinced themselves that they had done it, too, so he's not alone in that regard. It can drive you mad.

pghnative

2005-Oct-07, 08:36 PM

Maddad

Has it occurred to you that your tone is quite belligerant?

Has it occurred to you that if everyone on this thread thinks that you are wrong, that maybe just maybe you are indeed wrong.

Has it occurred to you that if everyone on this thread thinks that you are wrong, that calling everyone "stupid" reflects rather poorly on yourself?

What you have proven (that five regions cannot touch the other four) is necessary to prove the Four Colors Theorem, but it is not sufficient. Do you understand the difference between those two adjectives?

Edited to add: I've now read Grey's post, and he's explained the flaws in Maddad's logic much better than I. I'll keep the following paragraphs in since I do not wish to delete what I've posted, but I'll ask all to basically read Grey's explanation instead of mine.

Worzel's example shows multiple groups of four regions where none of four touches the other three. But three colors is not sufficient to color his map. Four is necessary. The point is that even if no territory touches more than X other territories, X+1 colors may not be enough.

What you need to do is show that multiple groupings of five reqions still can be colored with only four colors. And you need to do that for all types of multiple groupings. You have not done that.

ToSeek

2005-Oct-07, 09:20 PM

Maddad, your post is inappropriate.

You may not call people stupid or idiotic on this forum (or accuse them of not thinking). You have been banned for 24 hours. I would encourage you to use this period to actually read what people are telling you on this thread because - in my personal opinion - you could learn something.

I will also lock the thread for the duration so that the discussion will not continue without you.

ToSeek

2005-Oct-08, 10:37 PM

I've unlocked the thread.

Be nice!

worzel

2005-Oct-09, 08:42 AM

A month ago he jumped into this thread without a clue; look at his first two posts.What, you didn't get that I was joking?:rolleyes:

Putting your hands over your ears and shouting "I have so proved it" does't change the fact that you have not even attempted to show how proving that five regions can't all border each other proves the four color theorem. You seem to think the connection is too obvious to need explaining - well it's not.

All our supposedly irrelevant side tracking has been our well-intentioned attempts to get you to see the difference - but it all boils down to just that one missing connection.

Musashi

2005-Oct-09, 05:21 PM

I admit, when I first looked at the problem I thought that proving 5 territories couldn't all touch each other was sufficient, but through the conversations here and some thought on the issue, I realized that it wasn't.

peter eldergill

2005-Oct-09, 08:21 PM

I've unlocked the thread.

Be nice!

I'm always nice...I can't seem to click on any of the edit buttons right now, including quote and smilies!

Pete

Dragon

2007-Feb-21, 03:08 AM

...

One of the members here labeled someone an expert because they had supposedly come up with a proof. Never mind that nobody here can understand that proof. Never mind that we know of nobody who has verified it. Never mind that experts have been known to make mistakes. Never mind that the member making this interesting statement does not really know what qualifications this expert has to earn the title of expert. (Yes, I know you can know go look it up now, but you did not know when you were certain this man was the last word on the subject.) We have called them an expert, and from that concluded that the issue is settled and therefore needs no further investigation. What you are doing is insulating yourself from a need to think. Once you call him an expert, you need think no further.

...

Who was labelled an expert? (I'm an expert on this stuff and I'd like to read the "proof"; not to imply it's false).

On the other hand, is it just me, or do the dropdown boxes and smileys not work?

hhEb09'1

2007-Feb-21, 03:43 AM

Who was labelled an expert?Andrew Wiles

(I'm an expert on this stuff and I'd like to read the "proof"; not to imply it's false).Have you read his proof?

Dragon

2007-Feb-23, 10:10 PM

Andrew Wiles? In four-colour theorem!? Since when? I thought he stayed with the Taniyama-Shimura conjecture... Oh, well, guess not; but no, I haven't read his proof. Could you please post where I can read it? I'm really curious now, because he is a someone that might actually present a errorless proof.

hhEb09'1

2007-Feb-24, 02:40 AM

Andrew Wiles? Oops, my mistake. For some reason, I thought I remembered Maddad going on about Fermat's theorem. I think he was referring to Appel and Haken. But you better not take my word for it. :)

Dragon

2007-Feb-26, 12:33 AM

Whew. I was afraid my mathematical knowledge had fallen behind current events again. Well, I assume Appel and Haken's proof is correct; even if it isn't, the proof by Robertson, Sanders, Seymour, and Thomas is, and it is more hand-checkable. I bet Maddad would freak out if he reads his "proof" here (http://www.mathpages.com/home/kmath266/kmath266.htm) and the explanation of why it doesn't work, and will claim that it's been ripped off the boards. ;) j/k

Grey

2007-Feb-28, 05:27 PM

It wasn't so much that Maddad though those proofs were flawed, as that he thought they were needlessly complex. In particular, he thought that showing that one cannot have five mutually adjoining regions is sufficient to prove the four color theorem. The site you link to gives a simple explanation of why that is not enough.

peter eldergill

2007-Feb-28, 05:31 PM

Then he got mad at all of us for trying to show him why his proof wasn't sufficient....I don't even know if he still posts here.

I was hoping this thread went into the annals of obscurity

Pete

Ivan Viehoff

2007-Feb-28, 06:15 PM

There are thousands of Maddads out there. They think they have a wondrous proof, and are very unhappy when it is pointed out that they don't.

I've told this story somewhere else on this forum before, but it bears repeating. One of the top maths profs in Britain, I forget which, tells the story of how when first appointed he started getting all these manuscripts from amateurs. Initially he read them, perhaps hoping to find the next Ramanujan. But they were not, they were all erroneous. Initially he replied politely, pointing out the errors, giving constructive criticism and encouraging their interest in maths. He thought they would be pleased by the attention, but in fact they were very angry, and sent abusive letters in return, often accusing the establishment of a conspiracy to keep them down. So they just get a "I don't have time to look at your paper" acknowledgment now.

peter eldergill

2007-Feb-28, 08:59 PM

I think it may have been in this thread! I remember you, anyway

Pete

Dragon

2007-Mar-06, 03:40 AM

There are thousands of Maddads out there. They think they have a wondrous proof, and are very unhappy when it is pointed out that they don't.

I've told this story somewhere else on this forum before, but it bears repeating. One of the top maths profs in Britain, I forget which, tells the story of how when first appointed he started getting all these manuscripts from amateurs. Initially he read them, perhaps hoping to find the next Ramanujan. But they were not, they were all erroneous. Initially he replied politely, pointing out the errors, giving constructive criticism and encouraging their interest in maths. He thought they would be pleased by the attention, but in fact they were very angry, and sent abusive letters in return, often accusing the establishment of a conspiracy to keep them down. So they just get a "I don't have time to look at your paper" acknowledgment now.

Yeah, I've read this story somewhere, except the one I read ended with a "First mistake in the proof pointed out" response. Maybe it changed since then. If it hadn't, on the other hand, I'd like to mail him a proof of mine... too bad I don't have a copyright on it until July though...

peter eldergill

2007-Mar-06, 03:42 AM

Maybe we can all wait and you can post it here? (Not that I'll be able to understand it)

Pete

Dragon

2007-Mar-06, 03:49 AM

Wow, awesomely quick response, maybe I should rate this thread a 5. ;) But anyways, it's surprisingly simple. In fact, it's so simple I'm having people read it to make sure there's not a fatal flaw, which is why my school prohibited me from posting it until after I graduate. So far it's made it past two levels and is currently on the third. The next level is the state level, and after that gets done, I have to wait until July to post it in a journal. However, state level people generally stay busy a lot so it might not return thence much earlier than July.

Just by the way, how do I rate a thread anyways?

hhEb09'1

2007-Mar-06, 04:11 AM

[FONT="Fixedsys"] But anyways, it's surprisingly simple. This is a proof of the four color map theorem?

How many areas do you treat, in your proof?

grav

2007-Mar-06, 06:07 AM

Well, I have spent the last hour or so reading through this thread. It sounds interesting to me. I'm sure I've read about it somewhere before. After reading through what has been said here, I think I have come up with a simple proof. I will leave up to any of you to point out any potential flaws, which is possible, since I've barely had time to really think about it, but it makes sense to me and I don't see why it shouldn't be the case.

Let's say we start with a single territory and color it with color #1. Then we add territories all the way around it and alternate the colors with colors #2 and #3. Now, if the number of surrounding territories is even, then we would only require three colors. If it is odd, then we require an additional color #4 to fill in the gap. That's the first step.

The initial territory is now taken care of, being completely surrounded. So let's begin again with one of the outer ones. Each of the outer ones will be connected to the inner one and two other outer ones, correct? But whatever territories we connect to the main outer one will also be connected to one of the other two outer ones but not the inner one. So again, we just alternate the colors of the other two outer ones all the way around the main outer one. If the number surrounding it is even, then we stop there. If it is odd, then one of them must be a fourth color to fill in the gap. But since none of them will touch the inner one, we just use that color.

So basically, we can just keep adding new territories this way, by surrounding each territory in turn by alternating between it's two outer most adjoining territories' colors, and then adding the fourth "oddball" color if the number that surrounds it is odd, using whichever color remains that is not that of the main territory being surrounded or either of the original two that are alternated around it. And we should do this beginning with the inner-most territories and work our way outwards. We can continue doing this indefinitely on a flat surface. I'm not sure about 3D surfaces, though.

So how's that measure up for a proof? :) Is it sufficient?

grav

2007-Mar-06, 07:04 AM

Okay. Yup. Too simple. One extra rule is required. If the number of additional territories that is added on in order to surround the main outer territory is odd, so that the oddball color must be used, then that oddball color should be buried under any territories that exist past those that encompasses three or more of the ones that are being added on. In other words, if a territory beyond those that are presently being colored in touches three (or more) of them at the same time, then one of them will then become completely surrounded, and it should be the oddball. So all in all, only three of the colors should ever exist on the outer perimeter at any time.

hhEb09'1

2007-Mar-06, 07:16 AM

So how's that measure up for a proof? :) Is it sufficient?:) :) :)

Here's a country map:

6655

7224

7314

7344

8888

If I follow your directions, I think I paint #1 red, then #2 yellow, #3 blue, and #4 green. Continuing with the outer country #2, it is bordered by #4 green and #3 blue, so I start its perimeter by coloring #5 blue, #6 green, and I'm forced to use red for #7. This forces #8 to be yellow, right?

PS: I see you've modified your algorithm already. :)

So all in all, only three of the colors should ever exist on the outer perimeter at any time.Should? :) Now prove that you can do that.

PSS: I'm not sure, but my map may take care of your objection already. See, any finite map can be four-colored, we know that. (It's been proven :) ) The problem is stating an algorithm that is guaranteed to not get us into trouble, that will result in the map being four-colored. How would your new algorithm solve the problem in my map?

worzel

2007-Mar-06, 01:05 PM

In other words, if a territory beyond those that are presently being colored in touches three (or more) of them at the same time, then one of them will then become completely surrounded, and it should be the oddball.

What if there are no such territories?

peter eldergill

2007-Mar-06, 01:36 PM

But anyways, it's surprisingly simple. In fact, it's so simple I'm having people read it to make sure there's not a fatal flaw

Please don't forget that simple is such a relative term. I can assure you that to me, introductory limits and derivatives are extremely simple, as I have been teaching it for 10 years, but to my students....not so simple

Don't sell yourself short about a proof being too simple, although honestly, it does ring alarm bells...

Pete

grav

2007-Mar-06, 03:24 PM

:) :) :)

Here's a country map:

6655

7224

7314

7344

8888

If I follow your directions, I think I paint #1 red, then #2 yellow, #3 blue, and #4 green. Continuing with the outer country #2, it is bordered by #4 green and #3 blue, so I start its perimeter by coloring #5 blue, #6 green, and I'm forced to use red for #7. This forces #8 to be yellow, right?

PS: I see you've modified your algorithm already. :)

Should? :) Now prove that you can do that.

PSS: I'm not sure, but my map may take care of your objection already. See, any finite map can be four-colored, we know that. (It's been proven :) ) The problem is stating an algorithm that is guaranteed to not get us into trouble, that will result in the map being four-colored. How would your new algorithm solve the problem in my map?It does seem that my exception to the general rule has somehow turned my proof that it can be done into an algorithm for how it can be done. I'm not sure that it would be the same thing as a proof, then, unless I can prove that the exception will also never fail.

But as far as the algorithm goes, though, as an expansion to the same rule where one territory touches three or more of the inner ones, it appears that it also applies to any inner territory that touches three or more outer ones. That would be #2 in your map, since it touches #5, #6, and #7 on the third run. So on the last go around, we would color #5 blue and #7 green, making #6 the oddball red, being nestled within the other three. #8 would also be red, then, since we can never have more than three colors on the outer perimeter.

grav

2007-Mar-06, 03:25 PM

Quote:

Originally Posted by grav

In other words, if a territory beyond those that are presently being colored in touches three (or more) of them at the same time, then one of them will then become completely surrounded, and it should be the oddball.

What if there are no such territories?Then there is no problem. A complication only arises if one of the outer most territories touches at least three of the inner ones (or vice versa). But that is taken care of by what what discussed earlier in this thread, that no five territories can all touch each other at the same time, so one of them must be completely cut off. If we use the oddball color for that one, then it is then kept from obstructing the rest of the colors.

hhEb09'1

2007-Mar-06, 03:44 PM

It does seem that my exception to the general rule has somehow turned my proof that it can be done into an algorithm for how it can be done.It's not a proof--notice, you change your reasoning later on, for #2. How do you know that when you go back to change #2, that it doesn't screw up one of the alignments you made earlier?

grav

2007-Mar-06, 03:59 PM

It's not a proof--notice, you change your reasoning later on, for #2. How do you know that when you go back to change #2, that it doesn't screw up one of the alignments you made earlier?Yes, I know. It's not so much a proof now, just a method. I can only prove it so far for when no territory on the outer perimeter touches more than two inner ones. But as far as #2 is concerned here, one doesn't go back to change anything ever, they just kind of watch where they are going. ;) As long as all of the perimeter territories contain only one of three colors at a time, they are fine. I guess that also means starting with the oddball color each time, which makes a total of five rules now. I'll see if I can't make a computer program that will color in a screen full of random territories this way. I suppose the goal is to see if it can color them all in correctly the first time every time, without working backwards through the colors. Then I can show if the algorithm works, even if I can no longer prove it.

hhEb09'1

2007-Mar-06, 04:09 PM

I can only prove it so far for when no territory on the outer perimeter touches more than two inner ones.That fails for even my little map.

But as far as #2 is concerned here, one doesn't go back to change anything ever, they just kind of watch where they are going. ;)"Kinda watch where they are going..." :) :) :)

In other words, your algorithm is basically "We know we can do it, so we look at the whole map where we are going and figure out how to do it and then we do it." That's just worthless. :)

worzel

2007-Mar-06, 04:15 PM

Then there is no problem. A complication only arises if one of the outer most territories touches at least three of the inner ones (or vice versa)..

I see. So if this isn't a problem then we just end up choosing the oddball one at random. So I'd just need to think up one case where a random choice for the oddball would turn out, eventually, to be wrong and then your method would fail, right?

grav

2007-Mar-06, 04:44 PM

That fails for even my little map."Kinda watch where they are going..." :) :) :)

In other words, your algorithm is basically "We know we can do it, so we look at the whole map where we are going and figure out how to do it and then we do it." That's just worthless. :)We only need to watch for the territories that border the ones we are coloring, and we only need one to place the oddball color. After that, everything's fine. It does make things only slightly complicated, yes, and that can't be helped, so mistakes might be made in the process unless I can find a simpler way to explain it, but the proofcheck for our progress with each time we color in the surrounding territories of the main one is that the result would be that not more than three colors will ever exist on the outer perimeter at a time. Maybe I can explain it better after I make a program, since I can see the way I had the computer do it through the language of the program itself.

grav

2007-Mar-06, 04:46 PM

I see. So if this isn't a problem then we just end up choosing the oddball one at random. So I'd just need to think up one case where a random choice for the oddball would turn out, eventually, to be wrong and then your method would fail, right?That's right. It should always work with just the one first rule in that case.

hhEb09'1

2007-Mar-06, 05:04 PM

It does make things only slightly complicated, yes, and that can't be helped, so mistakes might be made in the process unless I can find a simpler way to explain it, but the proofcheck for our progress with each time we color in the surrounding territories of the main one is that the result would be that not more than three colors will ever exist on the outer perimeter at a time.That's not a proofcheck--if you ever get to that point, you will have failed. In other words you will need five colors to continue coloring.

You cannot just say, "we'll do that". We know we can do that because it has been proven, but you have to be specific in what you are going to do. Waving your hands and saying, we'll make sure that there's never four colors on the perimeter is not sufficient.

You can always make sure that there are only three on the perimeter--but that's just a restatement of the four color map theorem! That's what you're trying to prove!

I'm not sure I want to get involved here, as much of this is well beyond me, but I have a drawing that I just did that I can't see a way to color with only 4 colors. Maybe you guys can see how to do it.

Musashi

2007-Mar-06, 05:33 PM

http://img401.imageshack.us/img401/3215/mapzm5.png (http://imageshack.us)

hhEb09'1

2007-Mar-06, 05:36 PM

Maybe you guys can see how to do it.Color #2, #3, #4, and #5--you have to use all four colors, since each of them touches the other three. #1 has to be the same as #4 since it is the only one that it doesn't touch. #8 has to be the same as #3 since it is the only one it doesn't touch. And #7 has to be the same as #2, since it is the only one it doesn't touch.

PS: Just like Mushashi did! :)

Ahh, I got hung up on symmetry. Back to the shadows then.:)

hhEb09'1

2007-Mar-06, 05:41 PM

Ahh, I got hung up on symmetry. Rotate it through 180 degrees, it's the same diagram, with yellow exchanged for red, and red for yellow.

Rotate it through 180 degrees, it's the same diagram, with yellow exchanged for red, and red for yellow.

In my head, 3 and 7 had to be the same color. So did 4 and 8. For some reason nothing that I tried could change that.

hhEb09'1

2007-Mar-06, 05:49 PM

In my head, 3 and 7 had to be the same color. What kind of symmetry is that? :)

worzel

2007-Mar-06, 08:48 PM

I think your map, Tog_, proves grav's current method inadequate.

Starting with #5 as the middle one and grav's method we always end up with #2 and #3 being colored the same despite them bordering each other (there's an even number of adjacent territories so there's no oddball, strictly alternating).

grav, have you looked at Kempe's famously mistaken proof (http://www.stonehill.edu/compsci/LC/Four-Color/Four-color.htm)? It might give you some ideas for your attempt.

peter eldergill

2007-Mar-06, 09:17 PM

Grav, the fact that you're even attempting this is impressive to me

Pete

molinaro

2007-Mar-07, 01:15 PM

This thread sure had a disapointing ending.

So, was it the teachers who failed to teach or was the student not willing to learn? It seems like it would be the later that was the problem.

But would not a better attempt at teaching have resulted in a different outcome? I say this not to point fingers, but rather I just have to hope that it is possible to lead someone to a better understanding.

We know where Maddog went wrong. He made an assertion, that proving the impossibility of a k-5 planer graph is equivalent to proving the 4 color theorem. And when attempts were made to show that this was an assertion he resorted to the all to familiar cry of an unwillingness to learn. It seems that a reaction like that is all too familiar.

When you get to the point of trying to show exactly where they went wrong, they turn it into a fight against the establishment that is too stupid to see things in a new way.

How do we make them see the error of their ways? Is it always possible? Would a better aproach be more successfull? Should we be less eager to jump to the error that we see coming?

I just can't shake the feeling that it is a failure on the part of the smart people. Although it may just be wishfull thinking on my part that success should always be possible.

ASEI

2007-Mar-07, 01:37 PM

Didn't they have some sort of geometry with borders winding together tighter and tighter, with the four color theorum being violated at the singularity in the center?

PS- what about fractal geometries with infinitely convoluted shapes where, given a point, you can only tell if it is color 1 or 2 to some probability based on the number of iterations? :-P

WaxRubiks

2007-Mar-07, 03:02 PM

I came up with a possible sollution a few years ago, it involved just looking at the boarders only not looking at the thing as a 2d map. A map is basically made of countries each with a boarder and all you have to do is look at all the possible boarders and forget about the rest of the map.

I thought that it was the way to go.

http://img253.imageshack.us/img253/9898/4colourqj0.png (http://imageshack.us)

the numbers represent the colours.

It seems that if the number of intersection with boarder X toX is odd then you are going to need 4 colours if it is even all you need is 3.

Since all lines on a map are just boarders then maybe you can apply this idea to it whatever the shape of the map.

It may need some work to become an actual proof.

number 1 is the colour of the country that the boarder X to X encompases.

grav

2007-Mar-07, 03:59 PM

Well, it appears my proof has deteriorated even further from an algorithm to perhaps a few insights on how to possibly obtain an algorithm. I find I have to keep adding more and more rules for more complex situations. A computer might be able to keep up with them, but it's probably becoming almost humanly impossible otherwise. Oh, well. One of these days I might take Nereid's advice and post a reply after I've thought things completely through. Naah... What would be the fun in that? I like putting myself out there on the frontline sometimes. I'll either stand or I'll duck, drop, roll, and run for cover. It's more interesting, and I can learn something either way.

So what I'm doing now, instead of a compilation of rules that are almost impossible to keep track of and follow, is to try to find some mathematical basis for the geometry, which would automatically keep track of its own setup, by beginning with how many connections each territory has to the others, and then accounting for how each of those connected territories are connected also, by following some kind of numerical sequence where the result for each territory can then be hopefully divided by four so that the remainder gives the value for the color to be used, or something like that. It's kind of hit and miss so far, but this thing has caught my interest, and I know it's possible, so I'm going to keep working on it.

Grey

2007-Mar-07, 07:48 PM

I came up with a possible sollution a few years ago, it involved just looking at the boarders only not looking at the thing as a 2d map. A map is basically made of countries each with a boarder and all you have to do is look at all the possible boarders and forget about the rest of the map.

I thought that it was the way to go.Most analyses of the problem move from a map to an equivalent graph, where each territory is a point, and there are lines connecting any two points that share a border.

http://img253.imageshack.us/img253/9898/4colourqj0.png (http://imageshack.us)

the numbers represent the colours.

It seems that if the number of intersection with boarder X toX is odd then you are going to need 4 colours if it is even all you need is 3.I'm afraid it's not quite that simple, since a region's color may be constrained by what's happening at more than one border. For example, let's think about the two lowest regions labelled "2" in your drawing here. What if they touch? Well, then they can't both be color 2, and we'd need a fourth color. And what if they both touch the third region from the bottom labelled "2"? Well, then we'd either need a fifth color, or we'd need to redo the coloring scheme you've got to do it with only four.

Well, it appears my proof has deteriorated even further from an algorithm to perhaps a few insights on how to possibly obtain an algorithm. I find I have to keep adding more and more rules for more complex situations.That's why this is such a fascinating problem. It seems like it ought to be pretty easy to prove. And since we know that it is true, you'll never be able to come up with a counterexample. But to be able to actually demonstrate rigorously that there's no way to construct such a map is surprisingly difficult. It's all too easy to leave something out, or make an assumption that has not been proven, or fail to take into account some way of arranging things. An algorithm that show definitively how to color any map would be acceptable as a proof that it can be done, but only if you can show that the algorithm takes into account every possible case, and as I think you've realized, that's a lot harder than it sounds.

molinaro

2007-Mar-07, 08:48 PM

On that point, didn't the earlier posts talking about the computer proof say that it required 2000 seperate cases to be checked?

And a proper proof would of course need to include a proof that those are all the possible cases. Tough is an understatement!

worzel

2007-Mar-07, 10:14 PM

Any proof would have to prove it for an infinite number of cases to count. The question is, how easily can all infinite cases be proved. The current proof does require many cases to be considered separately (hence the computer), but who knows, many there's a much simpler proof out there waiting to be discovered.

ASEI

2007-Mar-08, 11:10 PM

Any proof would have to prove it for an infinite number of cases to count.

To violate the four color theroum, you would have to have a set of five countries, each of which touch the other four, within a 2D plane. If you cannot arrange five shapes so that they all touch each other in a plane, with non-overlapping territories, then you can't violate the theorum. Is that right?

01101001

2007-Mar-08, 11:47 PM

To violate the four color theroum, you would have to have a set of five countries, each of which touch the other four, within a 2D plane.

No. That would be sufficient to disprove it, but that is not necessary to disprove it. For instance, a contrived set of 105 countries that required 5 colors might also disprove it. So might such a set of 1001 countries.

If you cannot arrange five shapes so that they all touch each other in a plane, with non-overlapping territories, then you can't violate the theorum. Is that right?

No. If that were necessary and sufficient, you'd be home free on a proof. You could just enumerate all possible graphs of 5 nodes and show that all were 4-colorable.

ASEI

2007-Mar-09, 12:18 AM

But to make a 5th color necessary, wouldn't you have to have that specific situation somewhere on your map? It wouldn't matter between which countries, but you would need 5 of them to do what I outlined.

To make the 1st color necessary, you need one country.

To make the 2nd color necessary, you just need two to touch.

Third, three countries, each of which shares borders with all the others.

Four, four countries, each of which shares borders with all the others.

Ect...

Otherwise, you wouldn't have the necessary constraint, would you?

ASEI

2007-Mar-09, 12:29 AM

On different geometries (toruses, ect) you get the 7th, 8th, whateverth color by coming up with a situation where somewhere there exists a set of 7 countries, each of which touch borders with all the others, right?

hhEb09'1

2007-Mar-09, 01:44 AM

But to make a 5th color necessary, wouldn't you have to have that specific situation somewhere on your map?Prove that, and you have a proof :)

worzel

2007-Mar-09, 02:46 AM

To violate the four color theroum, you would have to have a set of five countries, each of which touch the other four, within a 2D plane. If you cannot arrange five shapes so that they all touch each other in a plane, with non-overlapping territories, then you can't violate the theorum. Is that right?

I'm too lazy to google one now, but there are examples of maps that are quite difficult to four color. While that doesn't prove anything, (other than that they are four colorable once you've found a way), trying made me quickly see why it wasn't as simple proving that five countries can't all touch each other.

If you end up four coloring twenty countries only to find that the twenty first needs a fifth color unless you backtrack, recoloring as you go until you reach an early decision that was, in retrospect, the wrong one (and think about how a constructive* proof would incorporate that), then one realizes (that's when I did, anyway) that this isn't going to be as easy one originally thought :)

* of course, the proof doesn't actually have to be constructive to count, but that seems to be the obvious approach to proving it - "look, you can always do it like this..."

worzel

2007-Mar-09, 02:52 AM

On different geometries (toruses, ect) you get the 7th, 8th, whateverth color by coming up with a situation where somewhere there exists a set of 7 countries, each of which touch borders with all the others, right?

If you can get n countries to all border each other then you will need at least n colours. We know you need at least 4 on the 2d plane becase we can make 4 countries all border each other. The theorem is that you will need at most 4 on the 2d plane.

Grey

2007-Mar-09, 02:18 PM

But to make a 5th color necessary, wouldn't you have to have that specific situation somewhere on your map? It wouldn't matter between which countries, but you would need 5 of them to do what I outlined.

To make the 1st color necessary, you need one country.

To make the 2nd color necessary, you just need two to touch.

Third, three countries, each of which shares borders with all the others.

Four, four countries, each of which shares borders with all the others.

Ect...

Otherwise, you wouldn't have the necessary constraint, would you?It's not quite that simple. We've brought up the issue earlier in the thread, but I'll just link again. Take a look at this page (http://www.mathpages.com/home/kmath266/kmath266.htm), and jump down to the fourth image. There you'll see a graph that only has two regions sharing a border with each other, yet requires three colors, and a graph with no more than three regions all sharing borders, and yet it requires four colors. Remember that although the color you use for a given region is only directly constrained by its immediate neighbors, it may be indirectly constrained by their neighbors, and the neighbors of those regions, and so forth.

So you can't assume that the maximum number of colors needed is the same as the largest group of mutually touching regions. Since there's a counterexample that shows that it's clearly not the case for two or three touching regions, you'd have to first prove that it holds for four, and that's not as easy as it sounds. It's a pretty common error, though; that's the exact mistake Maddad was making.

snarkophilus

2007-Mar-09, 10:32 PM

On that point, didn't the earlier posts talking about the computer proof say that it required 2000 seperate cases to be checked?

And a proper proof would of course need to include a proof that those are all the possible cases. Tough is an understatement!

There is a more recent proof (well, modification of the original) that only requires around 630 cases. However, the proof that those are sufficient is sufficiently difficult that it needs a computer. :p

Dragon

2007-Mar-14, 02:49 AM

First of all, I'd like to appologize I haven't been here for a while: I didn't check my email for too long; I need to switch the email address for this forum to a more frequently checked one. But anyways, here's to business.

First of all, thank you Tog_ (http://www.bautforum.com/showthread.php?p=941247)Tog_[/QUOTE] for the diagram: I had a similar one in my proof that I coloured using my theorem, and was going to post it but then I saw your'n. And as Peter Engergillsaid (http://www.bautforum.com/showthread.php?p=941084), simplicity is relativistic. When I said simple, I meant it did not have 2000 possibilities: it had 8 rules and 10 cases. So therefore, grav, you shouldn't give up: even if you get a lot of rules, if you can get your attempt (http://www.bautforum.com/showthread.php?p=942048) to work, you can probably get accredited with a new proof. Granted, it would be difficult, but you've got a nice idea. In fact, were my proof not completed, I might have wasted a summer to try to perfect your proof.

worzel

2007-Mar-14, 12:27 PM

As your proof is completed, Dragon, are you going to share it with us?

First of all, thank you Tog_ (http://www.bautforum.com/showthread.php?p=941247)Tog_ for the diagram: I had a similar one in my proof that I coloured using my theorem, and was going to post it but then I saw your'n. And as Peter Engergillsaid (http://www.bautforum.com/showthread.php?p=941084), simplicity is relativistic. [/quote]

But mine was shown to be invalid about... what, 7 seconds later. I never expected mine to be an example, I just couldn't get it work because I was hung up on something silly. I'm not sure I did much to help in any way at all. I would like to see your proof as well, however.

Dragon

2007-Mar-15, 01:46 AM

I appologize that my last post was so misshapen, but my computer was being difficult, so I was fortunate enough to get it up there as it is.

On a different note, I am not allowed to share my proof until after I publish it, and I am not allowed to publish it until July due to the copyright information agreement of the organization to whom I submitted it for revision. So once again, I appologize.

On a third note (man, I might as well compose a symphony ;)), Tog, your diagramme actually showed that grav's proof idea did not work; I don't see what you meant when you said it did not work.

worzel

2007-Mar-15, 02:29 AM

On a third note (man, I might as well compose a symphony ;))

One more and you'll be rivalling Beethovens famous intro :)

grav

2007-Mar-17, 04:29 AM

So therefore, grav, you shouldn't give up: even if you get a lot of rules, if you can get your attempt to work, you can probably get accredited with a new proof. Granted, it would be difficult, but you've got a nice idea. In fact, were my proof not completed, I might have wasted a summer to try to perfect your proof.

Thank you, Dragon. I appreciate that. Your comment prompted me to re-examine this puzzle more carefully, and then I realized, it's just that. It's a puzzle. As I was working through different possibilities, it reminded me of the number puzzles I like to work on, cross sums, where one tries to place digits in each row or column so that they add up to a specified number for that line. Each digit may only be used once and they must coincide with the numbers in the other lines at the same time. There are other similar puzzles, too, of course, like suduko. This is basically the same thing, but uses only four digits, and the geometry includes more than just columns and rows. Similar rules can therefore be applied, and that's just what I did. We wouldn't just throw down some digits and start backtracking when the number puzzle doesn't work out, so neither should we with this. It has an ordered logic to it.

Okay, so I figured it out, or so I say. :) I've only applied it to a couple of dozen random scenarios so far with about twenty territories each, give or take, but it worked the first time every time for every one. There is only one rule. Well, okay, three. But the first two are just common sense and constitute part of a proof. The third is the one that must be proven or disproven. So here we go (again). All we have to do is to begin by taking three territories that all touch each other with no space in between, and label them A, B and C, each representing a color. From this point on, we are just eliminating possibilities. All other territories are so far unmarked. Any unmarked territory means that four possibilities still exist for it. So we will only mark those for which we have determined that only one, two, or three possibilities remain.

All three rules must be followed in order with each run. We start with the most obvious. 1) If a territory is bordered by any three territories that have different labels that have already been determined, then the territory that borders all three must have the fourth label. See, told you it was common sense. Next rule, 2) If three territories all border each other, and two of them include the same two possibilities for their labels, then the third territory that borders them both does not include either. To demonstrate, if two territories that border each other include the possibilities A and D, then one is A and the other D, or one is D and the other A. Therefore, any territory that borders both of them will border an A and D regardless, so cannot include either. Finally, and this is the one to be proven or disproven, once a run has proceeded as far as it can with no further reduction in possibilities available, then one begins with the outer-most perimeter of territories that has been marked (containing two or three possibilities each) and works their way inward until one comes across a territory with only two possibilities. One may then choose either of the two possibilities for that territory they wish to label that territory. The run then begins again.

So this is how each run is performed. Beginning with our first three territories, we fill in the possibilities for all territories that surround them. There will be three for any that border only one of them, two for those that border two, and only one for any that touch all three, which can then be labeled as such. If any are labeled, then we begin the run again, by finding all of the possibilities for the territories that surround the one we just labeled as well. After we have done this until we get to the point that no more territories can be labeled, so that all territories on the outer perimeter so far contain either two or three possibilities each, we use rule number two. We must be very careful not to miss anything with these first two rules. It is very important. They can be especially difficult to catch sometimes. One must look at all territories that contain two possibilities one by one and be sure that no two bordering territories contain the same two possibilities. If they do, then one examines any territories that simultaneously border both of these and marks off those same two possibilities. If that leaves two left for the third one, then we continue with rule number two, checking also the third one in the same way since it now also contains two possibilities as well. If only one possibility remains for the third territory, then we label it as such and begin the run again (or complete rule #2 first and begin again, either way really in this case).

Finally, once both of the first rules have been exhausted, we find all territories that exist at the outer most perimeter for those that have been marked with two or three possibilities available. If any of those contain only two, then we can just pick one of them randomly to label that territory with and then start another run accordingly. If all of those on the outer-most perimeter contain three each, then we move to the next perimeter inward that doesn't include them and do the same thing, and so on. If no territories contain two possibilites, which would only occur if the territories share the same borders, then one may label any of them they wish, choosing from the possibilities given for the territory, of course.

A couple of points. First, if there is more than one territory containing two possibilities on the outer perimeter, which there usually are, then one may choose from any of them for rule number three (although now that I think about it, these are more steps than rules, since they must be followed in order). Second, when choosing a label for 'step' three, it is best to choose one that is contained in the most territories that border it, in order to eliminate more possibilities for them. But this is just a suggestion, not a rule. Anyway, that's it. One just continues steps one, two, and three, eliminating possibilities, until all territories are labeled. :D

hhEb09'1

2007-Mar-17, 04:39 AM

Anyway, that's it. :DNot quite. Now you have to prove it.

I'm betting that it doesn't work :)

Dragon

2007-Mar-17, 05:33 AM

Here is a graph which shows that your method does not work. Next time, could you be a little more careful when checking your algorithm? KMath266 (http://www.mathpages.com/home/kmath266/kmath266.htm) is a great site for examples (that's where I got this one). I understand you were just a beginner, and so were limited in the foresight of the failure. As soon as I read it, I could come up with an example, but it took like an hour to put it into a bitmap and another half hour to make another diagramme that is small enough to be uploaded.

Anyways, now that you see you have a contradiction, you might try to figure out what's wrong with your proof and correct it: I had to do that several times before I got mine to work on the ultimately difficult picture to colour. (I attached that too for you to try your methods on before you post them for me to check.) As a side note, your proof is starting to resemble my four-colour proof. :p Good luck.

HenrikOlsen

2007-Mar-17, 05:45 AM

Or alternatively, someone has to design a map that fails on the rules, which might be an interesting challenge as well. :)

Dragon

2007-Mar-17, 05:49 AM

OK, I posted a response a little while ago, but my computer is being difficult again, and the post doesn't come up. Here is an example of a counterproof, but upon revising your method, don't post again until they get my previous post moved hither, so that you could read more suggestions about it. Sorry, I don't remember what all the last post said, but I figured out what causes the problem and I hope this website will do something to fix the problem.

Edit: HenrikOlsen, I guess this answers your question. :)

It's just too bad that problem impedes my response that explained a lot of stuff.

peter eldergill

2007-Mar-17, 05:51 AM

But you only need to find one counterexample... my Calculus students often think they can find one example to prove a theorem or statement...I like to tell them that they got that one right, but there's an infinite number of other examples they have to show to be true...so one out of infinity changed to a mark out of 5... they often find that humourous (especially when we do limits)

Pete

Dragon

2007-Mar-17, 05:53 AM

Funny how everyone is up at this tremendously late hour. Or are y'all in a different time zone?

hhEb09'1

2007-Mar-17, 06:08 AM

Edit: HenrikOlsen, I guess this answers your question. Your diagrams seem to have a detached red region at the top. I don't think that grav's algorithm would produce that. Maybe I misunderstand something.

Dragon

2007-Mar-17, 06:34 AM

Oh, sorry, my bad, I misread his definition of outer, which he, by the way, would need to define better were this to be a formal proof. But at this point it does not matter because a counterproof is easy to come up with. I attach another example.

Dragon

2007-Mar-17, 06:38 AM

Why is everyone up so late anyways?

grav

2007-Mar-17, 06:40 AM

Your diagrams seem to have a detached red region at the top. I don't think that grav's algorithm would produce that. Maybe I misunderstand something.You're right, it wouldn't. At least not on the first run like that. The other three are fine to start with though.

grav

2007-Mar-17, 06:45 AM

Oh, sorry, my bad, I misread his definition of outer, which he, by the way, would need to define better were this to be a formal proof. But at this point it does not matter because a counterproof is easy to come up with. I attach another example.Boy, that was quick. The territory that is colored in the second picture should not be so yet. It has two possibilities, red or blue, and neither can be eliminated yet.

By the way, I guess it's about time I learned, how do I put pictures on here? It would probably ease this tremendously.

grav

2007-Mar-17, 06:50 AM

Oh, sorry, my bad, I misread his definition of outer, which he, by the way, would need to define better were this to be a formal proof. But at this point it does not matter because a counterproof is easy to come up with. I attach another example.Can you number the areas for that by any chance? That way, I can explain better.

HenrikOlsen

2007-Mar-17, 06:56 AM

Funny how everyone is up at this tremendously late hour. Or are y'all in a different time zone?

This is a worldwide board, there's people from all timezones here, plus lots who post at times that you wouldn't expect from their timezones.

Eg. I'm probably most prolific between 20:00 and 4:00, but with a large spread.

Incidentally, your use of font does makes your posts recognizable, but also harder to read.

Take a few minutes to consider which is most important.

Dragon

2007-Mar-17, 07:01 AM

Numbering the territories would make the file too big to fit within the limits of the upload, so we'll have to discuss it in terms of order of territories coloured.

...

All three rules must be followed in order with each run. We start with the most obvious. 1) If a territory is bordered by any three territories that have different labels that have already been determined, then the territory that borders all three must have the fourth label. See, told you it was common sense.

I did that for picture 1.

Next rule, 2) If three territories all border each other, and two of them include the same two possibilities for their labels, then the third territory that borders them both does not include either. To demonstrate, if two territories that border each other include the possibilities A and D, then one is A and the other D, or one is D and the other A. Therefore, any territory that borders both of them will border an A and D regardless, so cannot include either.

There are no territories that fall into that category.

Finally, and this is the one to be proven or disproven, once a run has proceeded as far as it can with no further reduction in possibilities available, then one begins with the outer-most perimeter of territories that has been marked (containing two or three possibilities each) and works their way inward until one comes across a territory with only two possibilities. One may then choose either of the two possibilities for that territory they wish to label that territory. The run then begins again.

I did that, and that is how I coloured the picture 2, to answer your question.

...

One must look at all territories that contain two possibilities one by one and be sure that no two bordering territories contain the same two possibilities. If they do, then one examines any territories that simultaneously border both of these and marks off those same two possibilities. If that leaves two left for the third one, then we continue with rule number two, checking also the third one in the same way since it now also contains two possibilities as well. If only one possibility remains for the third territory, then we label it as such and begin the run again (or complete rule #2 first and begin again, either way really in this case).

I could not quite understand this part.

...

Second, when choosing a label for 'step' three, it is best to choose one that is contained in the most territories that border it, in order to eliminate more possibilities for them. But this is just a suggestion, not a rule.

...And, I followed this suggestion when colouring.

Dragon

2007-Mar-17, 07:05 AM

This is a worldwide board, there's people from all timezones here, plus lots who post at times that you wouldn't expect from their timezones.

Eg. I'm probably most prolific between 20:00 and 4:00, but with a large spread.

Incidentally, your use of font does makes your posts recognizable, but also harder to read.

Take a few minutes to consider which is most important.

Harder to read? How? That's the first time I've been told that one.

As a side note, you can rid yourself of my font if you hold CTRL+scroll (decreasing or increasing font sizes on web pages) because my font only has a 10pt and a 16pt size; all other sizes get substituted with other fonts. If I'm not mistaken, Courier New for sizes larger than 10pt and Times New Roman for those smaller.

Dragon

2007-Mar-17, 07:34 AM

I hate to triple-post, but the posts are all addressing a different issue. I was going to wait until someone else posted to post this, but now I am getting ready to go to bed, and still no one posted, so I have little choice. To attach pictures, click on the "Manage Attachments" button in the "Additional Options" below the response box in advanced reply. It is fairly simple thence.

hhEb09'1

2007-Mar-17, 07:49 AM

Harder to read? How? That's the first time I've been told that one.OK, here's a second. :)

grav

2007-Mar-17, 08:13 AM

Sorry I took so long. The first three areas are already colored in, so we don't have to worry about them. So starting with the one to the left of the yellow one and working clockwise around the original three, we'll number them 1 through 6. Then from the one on the far left, 7 through 9. The color choices are represented by R, G, B, and Y.

Okay. So the possibilities for the ones surrounding the first three are:

1) RGB

2) RB

3) RBY

4) BY

5) GBY

6) GB

None of them cotain only one possibility, since none of the adjoining areas border all three, so step one is done. And no two of the six contain the same two color possibilities and border each other, so step two is done. So now we just pick one of the three with two colors and choose one of the two colors possibilities it contains (oh, you did do that right, sorry). So we'll pick 2R, as you have done in the second picture.

We now return to step one. We subtract R from the possibilities for any adjoining areas and include any additional ones in our set that also border it, which is only area 8 at this point. Now we have (not including the ones already colored in):

1) GB

3) BY

4) BY

5) GBY

6) GB

8) GBY

Rule #1 is taken care of, so we move to #2. There are two GB's and two BY's. 1 and 6 are both GB and border area 7, so area 7 becomes RY. 3 and 4 are both BY and border area 9, so area 9 becomes RG. We now have:

1) GB

3) BY

4) BY

5) GBY

6) GB

7) RY

8) GBY

9) RG

Okay. So rules #1 and #2 are now fulfilled. For #3, we start with the outermost areas with two or three possibilities and work inward. Those would be 7-9. If any of those contain two possibilities, then we choose one of them at random. So that third picture is incorrect for this, but I can see how that could be confusing. The outermost areas with two possibilities are 7 and 9. I'll choose 7. Then I'll choose Y for it. So none of the bordering territories can now contain Y as a possibility. That makes our set for those areas that are left uncolored:

1) GB

3) BY

4) BY

5) GB

6) GB

8) GB

9) RG

Moving through rule #1 and to rule #2 again, then, we find nothing changes. So back to rule #3. This time, let's go with 8B. So, back to rule #1, that makes 1G and 3Y. Then, in turn, 1G makes 6B, and 3Y makes 4B. Next, 4B makes 5G, and finally, 5G makes 9R. And that's all of them.

Hope that helps. :)

grav

2007-Mar-17, 08:27 AM

Not quite. Now you have to prove it.

I'm betting that it doesn't work :)Well, the first two rules are self-explanatory, basically common sense. And as far as I can tell, they cover all of the mandatory operations. When those two are no longer applicable, then, we can just about pick any possibility we wish from any of the areas that are left uncolored, and go from there. The only problem that I see with that, though, is why I started adding more rules in the first place when I started this a week ago. It occurs when an area becomes "isolated", buried underneath other areas. But if we work our way inward from the outer perimeter (of two or three possibility areas) when randomly choosing an area to color in, then we can get around that as well, so problem solved. I'm wondering if we could even pick randomly from an area with three possibilities and it still work out, but this is what I tried first, and it works out fine (so far, anyway), so that's what I'll stick with.

hhEb09'1

2007-Mar-17, 08:45 AM

Well, the first two rules are self-explanatory, basically common sense. I wouldn't call them common sense so much as mandatory. It seems to me if you violate them, you've failed.

And as far as I can tell, they cover all of the mandatory operations. When those two are no longer applicable, then, we can just about pick any possibility we wish from any of the areas that are left uncolored, and go from there.Now that seems like common sense--which is why I'm 99.999999% sure that this is doomed to failure. :)

That and your track record. :)

worzel

2007-Mar-17, 12:18 PM

Harder to read? How? That's the first time I've been told that one.

OK, here's a second. :)

And a third. :)

worzel

2007-Mar-17, 12:43 PM

When those two are no longer applicable, then, we can just about pick any possibility we wish from any of the areas that are left uncolored, and go from there.

If I had more time I'd take that example and systematically try every possible choice. If it failed for just one choice that'd prove that your algorithm doesn't work as advertised. Have you tried that?

If your algorithm works for any choice on that example then I'd try to construct a pathological case to make it fail for at least one choice.

But you'll get more kudos for finding a counter example yourself, you know, so I'll leave the checking to you :)

Dragon

2007-Mar-17, 01:57 PM

Well, so I guess you don't like my font. I'm just going to add the post at the bottom in my font then, just so that I could identify my posts easily. Too bad I can't make it show up one way for you and another way for me. But here are no other fonts that look good. Wish they'd let me use some of my other ones. Why is it hard to read?

But back to the proof. So I read his comment, and went back and did it again, and once again, failure. In this example, I coloured anything having a possibility of two colours with those two colours, and if aught had a possibility of three colours, I coloured it with a darker version of the fourth colour. Good luck fixing the problem.

--------------------------------------------------------

Well, so I guess you don't like my font. I'm just going to add the post at the bottom in my font then, just so that I could identify my posts easily. Too bad I can't make it show up one way for you and another way for me. But here are no other fonts that look good. Wish they'd let me use some of my other ones. Why is it hard to read?

But back to the proof. So I read his comment, and went back and did it again, and once again, failure. In this example, I coloured anything having a possibility of two colours with those two colours, and if aught had a possibility of three colours, I coloured it with a darker version of the fourth colour. Good luck fixing the problem.

worzel

2007-Mar-17, 02:18 PM

Hey Dragon, why don't you just make yourself an avatar if you want to see your posts quickly?

Dragon

2007-Mar-17, 02:22 PM

Well, you see, every thing that identifies me I want to have some sort of inspiration. For example, the font I use, I've been using ever since the old DOS computers that used it. Even everything on my computer, from default Internet Explorer font to the title bars of windows and names of files, is configured to have that font as a theme created back in the days, and it works still, even though WINDOWS XP technically no longer supports this font. I mean it's not in the dropdowns for the font you want anymore. So I just haven't had a chance to find a significant avatar. But how is my font hard to read?

----------------------------------------------------------------------------------------------

Well, you see, every thing that identifies me I want to have some sort of inspiration. For example, the font I use, I've been using ever since the old DOS computers that used it. Even everything on my computer, from default Internet Explorer font to the title bars of windows and names of files, is configured to have that font as a theme created back in the days, and it works still, even though WINDOWS XP technically no longer supports this font. I mean it's not in the dropdowns for the font you want anymore. So I just haven't had a chance to find a significant avatar. But how is my font hard to read?

Dragon

2007-Mar-17, 02:33 PM

Too bad I can't make it show up one way for you and another way for me.

Wait a minute, I was looking through posts; does this show up as my font to you? It does to me, but I suspect it's because it's considered the default font. If it does not for you, I could post everything inside code boxes, and then I'd recognize it's my post and it would appear normal for you.

Please note my post 211; they finally got it through.

--------------------------------------------------------

Please note my post 211; they finally got it through.

01101001

2007-Mar-17, 04:36 PM

Well, so I guess you don't like my font. I'm just going to add the post at the bottom in my font then, just so that I could identify my posts easily. Too bad I can't make it show up one way for you and another way for me. But here are no other fonts that look good. Wish they'd let me use some of my other ones. Why is it hard to read?

Please don't post everything twice just for your convenience. Please don't mess with the fonts. Or colors. Forget all that tempting decoration and just type your text in the style everyone is using. Look around. Be like your peers. Stop trying to make your words look weird. Thanks.

The font you chose is bitmapped, in need of anti-aliasing, looked even worse italicized in quoting, it was monospaced. It looked bold. It was ugly. It was hard to read. You don't want your words to look ugly and hard to read do you?

Dragon

2007-Mar-17, 05:03 PM

Well, at first, posting everything twice seemed to solve the problems:

1. You could read it well because I had a regular font too.

2. I could find my posts because they include my font.

3. It was convenient for the both of us, because I can read the regular font too rather than reading the text at the bottom, so as long as both of us read the top, it worked.

However, the more I thought about it, the more it seemed redundant. So I thought about putting my font into a signature. But then the signature needs to be long so as not to be inconspicuous, and I cannot think of anything which long and useful. So any suggestions about what to do?

I can see that people can see it as bold and ugly, but how is it difficult to read?

---------------------------------------------------------------------------------------------------

Well, at first, posting everything twice seemed to solve the problems:

1. You could read it well because I had a regular font too.

2. I could find my posts because they include my font.

3. It was convenient for the both of us, because I can read the regular font too rather than reading the text at the bottom, so as long as both of us read the top, it worked.

However, the more I thought about it, the more it seemed redundant. So I thought about putting my font into a signature. But then the signature needs to be long so as not to be inconspicuous, and I cannot think of anything which long and useful. So any suggestions about what to do?

I can see that people can see it as bold and ugly, but how is it difficult to read?

grav

2007-Mar-17, 05:50 PM

If I had more time I'd take that example and systematically try every possible choice. If it failed for just one choice that'd prove that your algorithm doesn't work as advertised. Have you tried that?

If your algorithm works for any choice on that example then I'd try to construct a pathological case to make it fail for at least one choice.

But you'll get more kudos for finding a counter example yourself, you know, so I'll leave the checking to you :)Actually, that would be part of a proof for it, by trying every possible choice. That's actually how I found that this works in the first place, so I'll explain how that works as well. I just didn't want to get into all of that right off the bat since I knew rule #3 would be difficult to explain to begin with.

Okay. So here's what I actually did. I wanted a rigid proof, so I only eliminated possibilities according to rules #1 and #2, which are definite. It really doesn't matter what order those two are performed in. But after those two are exhausted, then what? Well, I took an area with two choices and tried a run for each one, placing the one I originally chose in a box and eliminating possibilities for other areas with a left to right diagonal slash through. I generally picked an area that had the most potential of eliminating possibilities for other areas, usually those with the most areas bordering it. Any other areas where the color was determined this way I also used a box around that possibility to show it. When all of the possibilities for rules #1 and #2 have been used, I then started back by setting a triangle around the other possibility for the same original area and doing the same thing with the other areas, this time eliminating possibilities with a right to left diagonal slash and setting triangles around the possibilities for other areas that are determined this way.

Now, after doing all of that, one can tell which possibilities for which areas can be determined to be a specific color, because they will have both a box and a triangle set around the same possibility for that area. So since the original area we started with led to the same possibility for another, and that is all of the possibilities for the original area, then any possibilities for any other areas that are both boxed and triangled must be definite, so the color for that area is now determined. Likewise, any possibilities for any other areas that contain a diagonal slash in both the left to right and right to left directions are therefore not used for either possibility in the original area, so those possibilities for the other areas are now crossed off. After doing all of this, we then start the run over. Now, I could have and probably should have explained it this way to begin with, but when I found a pattern that showed that using any possibility for any area on the outer perimeter with two possibilities came to the same conclusion, I started using that instead, and so far it has worked out every time.

Dragon

2007-Mar-17, 05:54 PM

Grav, did you look at my illustrations?

---------------------------------------------------------------------------------------------------

Grav, did you look at my illustrations?

grav

2007-Mar-17, 06:00 PM

But back to the proof. So I read his comment, and went back and did it again, and once again, failure. In this example, I coloured anything having a possibility of two colours with those two colours, and if aught had a possibility of three colours, I coloured it with a darker version of the fourth colour. Good luck fixing the problem.I would have to see what you did to see where you may have gone wrong. I'm probably just not explaining it well enough.

hhEb09'1

2007-Mar-17, 06:07 PM

and so far it has worked out every time.Now, all you have to do is prove that it always works :)

Dragon

2007-Mar-17, 06:11 PM

Grav, did you look at my illustrations?

I would have to see what you did to see where you may have gone wrong.

Guess not. Well, here, I'm just going to re-post both of the diagrammes: don't miss the clickable links at the bottom. In the meanwhile, someone suggest what I can do about the font dilemma.

---------------------------------------------------------------------------------------------------

Guess not. Well, here, I'm just going to re-post both of the diagrammes: don't miss the clickable links at the bottom. In the meanwhile, someone suggest what I can do about the font dilemma.

grav

2007-Mar-17, 06:23 PM

Now, all you have to do is prove that it always works :)You know, now that I think about it, I will just substitute rule #3 for the method I just stated, which is much more rigid and obvious, even if it is the long way around, for now anyway. I can show why choosing a random possibility from an area on the outer perimeter with two possibilities works out at a later time, since I really don't know, I just see that it does. So now all I have to prove is that there will be at least one area with two possibilities and that it will lead to at least one possibility for another area being determined or cancelled out each time. There always will be at least one area with two possibilities unless the inner areas share all of the same "cross-wise" borders with the outer ones, in which case we would have to use rule #3 for all three possibilities.

Dragon

2007-Mar-17, 06:34 PM

And for all the people who ask you to prove stuff, don't worry about it. Once I see that your method works, I can come up with a proof. I am fairly good at making algorithms that would come up with counterexamples, and once your proof works, the algorithm will just lead to a contradiction, meaning that it is impossible to come up with a counterexample. That would be sufficient to show that your proof works.

---------------------------------------------------------------------------------------------------

And for all the people who ask you to prove stuff, don't worry about it. Once I see that your method works, I can come up with a proof. I am fairly good at making algorithms that would come up with counterexamples, and once your proof works, the algorithm will just lead to a contradiction, meaning that it is impossible to come up with a counterexample. That would be sufficient to show that your proof works.

hhEb09'1

2007-Mar-17, 06:40 PM

So now all I have to prove is that there will be at least one area with two possibilities and that it will lead to at least one possibility for another area being determined or cancelled out each time. There always will be at least one area with two possibilities unless the inner areas share all of the same "cross-wise" borders with the outer ones, in which case we would have to use rule #3 for all three possibilities.You mean like this:

1 1 2 2

1 R R 2

4 G B 3

4 4 3 3

None of the areas 1, 2, 3, or 4 have only two possibilities.

hhEb09'1

2007-Mar-17, 06:42 PM

[FONT=Georgia]And for all the people who ask you to prove stuff, don't worry about it. Once I see that your method works, I can come up with a proof. I am fairly good at making algorithms that would come up with counterexamples, and once your proof works, the algorithm will just lead to a contradiction, meaning that it is impossible to come up with a counterexample. That would be sufficient to show that your proof worksEh?

That's what this whole discussion is about, a proof. :)

grav

2007-Mar-17, 06:47 PM

Guess not. Well, here, I'm just going to re-post both of the diagrammes: don't miss the clickable links at the bottom. In the meanwhile, someone suggest what I can do about the font dilemma.

---------------------------------------------------------------------------------------------------

Guess not. Well, here, I'm just going to re-post both of the diagrammes: don't miss the clickable links at the bottom. In the meanwhile, someone suggest what I can do about the font dilemma.Sorry. I didn't notice that. In the first attachment, the third image has areas 2 and 3 with the same two possibilities, blue and yellow. That means rule #2 must be applied before we go any further, so area 8 is green or red. Only then can we go to rule #3 and choose a color for an area on the outer perimeter, which would include areas 5, 6, or 8. We cannot choose any for areas 2 or 3 yet, because they then lie further in.

[EDIT-Whoops. Scratch that. I almost did the same thing there. In the third image, areas 5 and 6 also contain the same possibilities, so we must also set area 9 at red or green. That leaves only two possible areas to choose from on the outer perimeter at this piont, areas 8 and 9.]

Dragon

2007-Mar-17, 06:56 PM

I know, but as long as my counterexample stands (post 242, sorry, I'm not allowed to post hyperlinks to posts until I have a total of at least 30 posts), coming up with a proof is pointless, because you know the proof will fail and show that there is a counterexample. Also, that second diagramme on post 242 is for grav to colour with his revised method before he posts it, because that is the diagramme that caused Alfred Kempe's 1890 proof to fail. Chances are, that diagramme can make almost any false proof fail; I attach another diagramme that shows what Alfred Kempe's proof got the fc diagramme down to when it failed.

Edit: As you should be able to tell, he used a method slightly different from yours: he started with the points that have more than 5 areas touching them.

---------------------------------------------------------------------------------------------------

I know, but as long as my counterexample stands (post 242, sorry, I'm not allowed to post hyperlinks to posts until I have a total of at least 30 posts), coming up with a proof is pointless, because you know the proof will fail and show that there is a counterexample. Also, that second diagramme on post 242 is for grav to colour with his revised method before he posts it, because that is the diagramme that caused Alfred Kempe's 1890 proof to fail. Chances are, that diagramme can make almost any false proof fail; I attach another diagramme that shows what Alfred Kempe's proof got the fc diagramme down to when it failed.

Edit: As you should be able to tell, he used a method slightly different from yours: he started with the points that have more than 5 areas touching them.

grav

2007-Mar-17, 07:04 PM

You mean like this:

1 1 2 2

1 R R 2

4 G B 3

4 4 3 3

None of the areas 1, 2, 3, or 4 have only two possibilities.Yep. That would be it. We would have to run through all of the possibilities for that, with reference to any other surrounding areas.

Dragon

2007-Mar-17, 07:11 PM

...

In the first attachment, the third image has areas 2 and 3 with the same two possibilities, blue and yellow. That means rule #2 must be applied before we go any further, so area 8 is green or red.

I went from image 3 to image 4 by applying rule 2. Then I recoloured the map to show the possibilities for the remaining territories.

...

In the third image, areas 5 and 6 also contain the same possibilities

...

So I applied rule 2 there, and then more of rule 1 to go from 4 to 5.

In case you didn't understand what I did, I attach an image with a more detailed step-by-step procedure of what I did. This time it's going from up to down. If you can colour the map, please attach a step-by-step bitmap (not just text, that gets confusing and takes too long to draw in order to look at it) like I did.

---------------------------------------------------------------------------------------------------

In case you didn't understand what I did, I attach an image with a more detailed step-by-step procedure of what I did. This time it's going from up to down. If you can colour the map, please attach a step-by-step bitmap (not just text, that gets confusing and takes too long to draw in order to look at it) like I did.

Powered by vBulletin® Version 4.2.3 Copyright © 2021 vBulletin Solutions, Inc. All rights reserved.