Four Color Map

Factual Questions
21

[QUOTE=Exapno Mapcase]
Sorry, I got called away and I should have hit preview instead of submit.

What I should have continued to say is that the mathematical proof of the sufficiency of four colors cannot be given by doodling connections on a piece of paper. Mathematical maps are far more complex than a series of areas. Colophon’s naive explanation fails because it cannot account for the cascade of color changes that are made possible by any new connection or area. The mathematical proof must account for cases of near-infinite complexity that cannot be approximated by drawing a circle and coloring in the interior. This is in fact precisely why all earlier attempts, including those by people who spent years drawing ever-more complex partitions, failed. Blaster Master’s four color theorem link has an example of exactly why this is the wrong approach.
[/QUOTE]

I appreciate that such an approach cannot lead to a proof; I was merely observing how it is odd that something so “obvious” is at the same time so difficult to prove. When my maths teacher first mentioned this problem and invited us to try and find a counterexample, I “knew” within half an hour that it would never be possible, just by observing the way the linkages work. OK, you could argue that in a nearly infinitely complex map, something weird could happen, but you can’t get away from the basic fact that adding one connection necessarily removes another connection elsewhere in the map, if the regions being connected are currently necessarily of the same colour.

Call it naive if you like, but it’s clearly true, as the proofs by other methods indicate!

22

It can’t really be proved using regular, traditional proofs, but is nontheless true. Perhaps axiom would be better? I also think it’s just a quirk of geometry that bugs people.

23

[QUOTE=Colophon]
Call it naive if you like, but it’s clearly true, as the proofs by other methods indicate!
[/QUOTE]

It’s entirely possible that your conjecture is false even though the four-color theorem is true, unless you can provide a proof otherwise.

24

[QUOTE=garygnu]
It can’t really be proved using regular, traditional proofs, but is nontheless true. Perhaps axiom would be better? I also think it’s just a quirk of geometry that bugs people.
[/QUOTE]
The proof is regular - as regular as any, as airtight as any. Just like any proof, the only problem would be if one of the steps contained a logic error. It’s just a long proof is all.

Colophon - I think I see what you’re saying. Sort of a proof by induction. If you start with a map that only requires four colors, there’s no region you can add or split that would necessitate a new color. Since every map could be ‘built up’ from a map that at some point needed only 4 colors, you never need more than 4.

However, neither of two statements are obvious enough to me that I accept them.

Starting with the second, why couldn’t a map with 8 regions requiring only 3 colors get one new region which suddenly required 5 colors?

As for the first, if you have a map that needs 4 colors, I don’t see why you can’t add a region that does not necessitate splitting two extant regions.

BTW, I’ll never accept your spelling of ‘color.’ My wife and I had a big argument when we got married about how to spell ‘honor’ on our wedding invitations. I thought we might as well raise the Union Jack over the White House as spell it her way.

25

[QUOTE=Colophon]
you can’t get away from the basic fact that adding one connection necessarily removes another connection elsewhere in the map, if the regions being connected are currently necessarily of the same colour.
[/QUOTE]

(Pssst… necessarily of different colors… Regions are never necessarily the same color.)

26

Sometimes they are. Suppose you have two concentric circles, and divide the region between them into three sectors. Then for a four-coloring, the bulls-eye region must be the same color as the exterior region.

27

[QUOTE=bup]
(Pssst… necessarily of different colors… Regions are never necessarily the same color.)
[/QUOTE]

No, I do mean the same colour, otherwise bringing them in contact wouldn’t cause a problem.

Look at File:4ct-non-counterexample-2.png - Wikipedia again.

To satisfy four-colouring, one of the opposite pairs of circle segments has to be coloured the same colour, e.g. the blue quarters of the inner ring.

Now, if we were to bring them into contact with one another, we could form pathways in a number of ways, either across the middle of the centre circle, or between the circle and the middle ring, or between the middle and outer rings, or even take a snake-like pathway looping outside the circles altogether.

But however we link them, we are always destroying connections somewhere else… say we take a pathway from one blue quarter to the other, around the inner perimeter of the centre green circle. We have now destroyed the connection between the green circle and the orange quarter, or the green circle and the purple quarter, depending where we drew it.

I somehow don’t think I’m getting my point across…

28

Looking at the circular picture you linked to, if we connect the two green connections on the outer top and bottom (by going around the circle), which connection have we broken?

We can even do this in a way that creates an entirely new region connected to both of the old ones, which seems a further complication.

29

[QUOTE=Jebus H. Christ]
I understand that any two-dimensional map can be filled in using only four colors. But I can find out how to fill in this map with only four colors.

If I may be permitted a slight hijack, may I say that I find your user name insensitive and patently offensive.

30

[QUOTE=panamajack]
Looking at the circular picture you linked to, if we connect the two green connections on the outer top and bottom (by going around the circle), which connection have we broken?
[/QUOTE]
You’ve disconnected the outer field of blue from the purple arc of the outer circle (if you go around the left). However, that disconnection has not allowed either the purple area nor the blue to change to a new color.

So, colophon, I understand a bit more what you’re saying this time, but still don’t see it as making 4-colors max intuitive.

Couldn’t you apply your “reasoning” to a 3-color map? Any time you connect two similar-colored regions, you’re dividing two others (or one into two). How, then, could it be possible to ever require 4 colors?

31

[QUOTE=bup]
The proof is regular - as regular as any, as airtight as any. Just like any proof, the only problem would be if one of the steps contained a logic error. It’s just a long proof is all.

[/QUOTE]

I have a warm spot for this - I was at Illinois when it was proved, and was at one of the first (if not the first) public lectures by Hakken and Appel on it. Plus, I taught Andy Appel and Dorthea Hakken PDP-11 assembler. :slight_smile: Andy stole time on the Cyber running PLATO for the ennumeration of the possible configurations needed for the proof.

I think the reason it was controversial was that though any proof has to be checked for logic errors, this one might be incorrect if there was a programming error. That can’t be checked in the traditional way. Software verification was not at the state where it could be verified at the time - I don’t know if the code ever was verified.

32

[QUOTE=Mathochist]
Incidentally, IIRC it’s only really difficult on genus-zero surfaces. For higher genera the analogous theorem is easier to prove.
[/QUOTE]

Yep. Robin Wilson’s Four Colours Suffice (Penguin, 2002) is even able to run through a conceptually complete proof that it’s a Seven-Colour-Theorem on a torus at pretty much a pop-maths level.

33

[QUOTE=Joe Mahma]

[QUOTE=Jebus H. Christ]
I understand that any two-dimensional map can be filled in using only four colors. But I can find out how to fill in this map with only four colors.

If I may be permitted a slight hijack, may I say that I find your user name insensitive and patently offensive.
[/QUOTE]
Joe Mahma, the right thing to do would be to email the mods, not post your comments in GQ.

Please do not repeat this.

Thanks.

-xash
General Questions Moderator

34

[QUOTE=bup]
Couldn’t you apply your “reasoning” to a 3-color map? Any time you connect two similar-colored regions, you’re dividing two others (or one into two). How, then, could it be possible to ever require 4 colors?
[/QUOTE]

The reasoning doesn’t work because you can go from a 3-colour to a 4-colour map without breaking a connection.

E.g. if you have a red square touching a blue square, both inside a green circle: http://i4.tinypic.com/1040z7r.gif

you can simply add another square inside the circle, touching both the first two squares, and it has to be a fourth colour, say yellow: http://i4.tinypic.com/1040zlf.gif
But now you cannot introduce another region that touches all three of those those squares without breaking a connection between at least one of them and the outer circle. It’s just geometrically impossible - in order to form a continuous pathway from one to the other, it cuts off another section.

Let’s try: http://i4.tinypic.com/10411jk.gif That’s no good - it has separated the blue square from the green circle, so now the blue square can be coloured green. And if we take the left hand edge of the new purple region a bit to the right, allowing the blue square to be in contact with the green circle, we have now broken contact with the red square, so the new region could be coloured red. And so it goes…

OK, so what if we take the pathway outside, and not directly in contact with the other square the whole way round? http://i4.tinypic.com/104120z.gif
The new region is touching all three squares, and the green circle. But again, the blue square is cut off from the outer green circle, so there is nothing stopping it from being coloured green, once the “new” mini sections are recoloured appropriately: http://i4.tinypic.com/10412j5.gif And there we are back to our four colours again.

Or we could have the new section touching all three squares by cutting across the middle of them: http://i4.tinypic.com/10414c4.gif

But you still can’t avoid breaking connections - now the main area of the blue square is cut off from the main area of red square, so they can be coloured the same, and the small corner of red is cut off from the yellow, and the small corner of blue is cut off from the green. Again 4-colour is restored: http://i4.tinypic.com/10414sh.gif

Or you could go right outside the circle: http://i4.tinypic.com/10415c3.gif
But that doesn’t help either because you are ALWAYS breaking connections elsewhere in the map: http://i4.tinypic.com/10415pz.gif

All of which is pointless of course, but I find it interesting…

35

[QUOTE=garygnu]
It can’t really be proved using regular, traditional proofs, but is nontheless true. Perhaps axiom would be better? I also think it’s just a quirk of geometry that bugs people.
[/QUOTE]

Just because we don’t know a non-computer-based proof doesn’t mean one doesn’t exist, or do you have some sort of proof that it can’t be proven otherwise?

Besides, the computer-based proof is really just a reduction to cases like many “regular” proofs are – there’s just a whole lot of them. The problem (as others have stated) is that it’s difficult to check the proof without simply trusting the programmers and the compiler. However, the same charge can be levelled at the classification of finite groups due to its sheer length rather than anything involving a computer, and nobody seriously thinks that’s in doubt.

36

[QUOTE=xash]

[QUOTE=Joe Mahma]
Joe Mahma, the right thing to do would be to email the mods, not post your comments in GQ.

Please do not repeat this.

Thanks.

-xash
General Questions Moderator
[/QUOTE]

OK. Sorry.

37

Supplementary question: In real-world maps (ie. ones that actually depict a variety of countries in relation to each other, rather than theoretical shapes), would it be possible to have a set of mixed-up countries that violated the four-colour theorem? I’m thinking of something like Germany 1918-1939, which was split roughly in half by the “Polish corridor”, which meant that you has a chunk of Germany (which needs to be the same colour as the rest of Germany) of in the middle of Poland. Could you therefore design a set of countries where the four-colour theorem would no longer hold?

38

No. The theorem holds for any map drawn on a plane.

39

The Wikipedia article mentions real world counter examples, where the graph becomes disconnected and therefore not four-colourable.

40

Sorry, non-planar, not disconnected.