## Four color theorem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Four color theorem

skeptical scientist wrote:Well, since classification is only supposed to be up to isomorphism, it's really quite easy. In fact there is a simple invariant which completely classifies the finite sets up to isomorphism.

Sigh, my humor once again falls victim to being taken seriously.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Four color theorem

mike-l wrote:Woohoo!, my humor once again falls victim to being taken SRSLY.

I recognized it as humor, I just demand that my mathematical humor be mathematically rigorous.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Four color theorem

skeptical scientist wrote:
mike-l wrote:Woohoo!, my humor once again falls victim to being taken SRSLY.

I recognized it as humor, I just demand that my mathematical humor be mathematically rigorous.

Ah, perhaps then I fell victim to taking you seriously!
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Suffusion of Yellow
Posts: 42
Joined: Thu Jan 01, 2009 6:15 pm UTC

### Re: Four color theorem

mike-l wrote:Classification of finite sets is a very difficult and untractable problem, unlike finite groups which took a mere 1500 pages.

Oh Jesus. Oops.

Though actually isn't it simple finite groups

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Four color theorem

Suffusion of Yellow wrote:
mike-l wrote:Classification of finite sets is a very difficult and untractable problem, unlike finite groups which took a mere 1500 pages.

Oh Jesus. Oops.

Though actually isn't it simple finite groups

Good point. In that case, there is one finite simple set
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

### Re: Four color theorem

Isnt the jordan curve theorem something that was also proved by computer?

supremum
Posts: 69
Joined: Sat Dec 12, 2009 8:58 pm UTC

### Re: Four color theorem

BlackSails wrote:Isnt the jordan curve theorem something that was ALSO YOU GUYS: proved by Pornography Storage Apparatus?

Nope, it's actually not that hard to prove if you're willing to use algebraic topology.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Four color theorem

I get the impression that the proof that checkers is a draw assuming optimal play from both players is OH HAI I HAZ A COREDUMP with a game tree with trillions of states.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

### Re: Four color theorem

Tirian wrote:I get the impression that the proof that checkers is a draw assuming optimal play from both players is OH HAI I HAZ A COREDUMP with a game tree with trillions of states.
Indeed it is, and if you play against the full power of Chinook, you can never win.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

### Re: Four color theorem

Suffusion of Yellow wrote:Classification of finite sets, its 1500+ pages, but each part of the proof has been checked and verified

Assuming that you meant Classification of FInite Simple Groups, as you appear to have done so, CFSG took many more than 1500 pages. Try adding an extra 0 on the end. The Aschbacher--Smith quasithin case is 1500 pages according to my bookshelf, and the Gorenstein--Lyons trichotomy theorem is 700 pages. Each of the dihedral, quasidihedral, and wreathed classifications were 200 pages. That gets you close on 3000 pages and we've only done some of it.

Fume Troll
Posts: 254
Joined: Wed Jan 13, 2010 8:06 am UTC
Location: Scotland / Norway mainly

### Re: Four color theorem

What about more or less dimensions? I suppose in 1D you only need two colours (think alternately coloured "dashed" line), but in 3D...do you need an infinite number of colours? I think you must.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Four color theorem

Fume Troll wrote:What about more or less dimensions? I suppose in 1D you only need two colours (think alternately coloured "dashed" line), but in 3D...do you need an infinite number of colours? I think you must.

Yes, you can embed [imath]K_n[/imath] in 3 space because, among other things, a curve doesn't split the space into 2 regions.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Four color theorem

How about 3d with convex volumes to colour?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

gmalivuk
GNU Terry Pratchett
Posts: 26836
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Four color theorem

I think it's still infinite, and there was a link to a relevant theorem in another thread about n-color theorems.

Edit: Yeah.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Fume Troll
Posts: 254
Joined: Wed Jan 13, 2010 8:06 am UTC
Location: Scotland / Norway mainly

### Re: Four color theorem

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

### Re: Four color theorem

mike-l wrote:
Fume Troll wrote:What about more or less dimensions? I suppose in 1D you only need two colours (think alternately coloured "dashed" line), but in 3D...do you need an infinite number of colours? I think you must.

Yes, you can embed [imath]K_n[/imath] in 3 space because, among other things, a curve doesn't split the space into 2 regions.

I was thinking of how to give a visual proof of an embedding of [imath]K_n[/imath] into 3-space, and I came up with the following.

Consider n points spaced equally on the circle, and consider a plane moving from each point to each other point in a straight line, so n(n-1)/2 planes in all. They reach their cruising altitude very quickly, say with [imath]\epsilon[/imath] of taking off, and land within [imath]\epsilon[/imath]. If each plane has a different cruising altitude, no two flightpaths will cross, at least for some sufficiently small [imath]\epsilon[/imath] so that no plane travelling between two points gets within [imath]\epsilon[/imath] of another point on the circle.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: Four color theorem

Wait, how does that require infinitely many colours? Surely you could colour, say, the horizontal stripes as alternating 1 and 2, and the vertical stripes as alternating 3 and 4... and thus 4-colour the whole set, regardless of how many stripes there are...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Four color theorem

Good catch.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Fume Troll
Posts: 254
Joined: Wed Jan 13, 2010 8:06 am UTC
Location: Scotland / Norway mainly

### Re: Four color theorem

I assumed that (since the rods shown have the same colours) the vertical and horizontal rods are the same rods, having been bent outside the image to meet themselves at the point shown, so that every rod touches every other. By extension, this would demonstrate a case which would require infinitely many colours.

gmalivuk
GNU Terry Pratchett
Posts: 26836
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Four color theorem

The edges are drawn wrong, but I think in that demonstration the perpendicular regions with the same color are meant to be contiguous (and thus it's not a proof for the convex case, but it does show why no finite number is sufficient in the general case).
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

bojanglin
Posts: 2
Joined: Thu May 06, 2010 1:36 am UTC

### Re: Four color theorem

I don't think I understand the theorem correctly. I mean, it applies for REAL or IMAGINARY boundaries, right?

Alright, correct me if I'm wrong. The theorem says that for any flat map, real or imaginary, the divisions need only be colored with four colors. No adjacent side of any same-colored division are allowed to touch...they can touch at points, though.

See attached file. I think I am missing out on something, or else this would disprove the theorem. Or are we looking for some mathematical proof as opposed to drawing a picture or something?
Attachments

BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

### Re: Four color theorem

Change the green to red, then make the center square green.

bojanglin
Posts: 2
Joined: Thu May 06, 2010 1:36 am UTC

### Re: Four color theorem

Oohh that's a good one!

My friend and I kept trying to think up of examples and eventually we got that one. Can't wait to see the disappointed look on her face. :]

Fume Troll
Posts: 254
Joined: Wed Jan 13, 2010 8:06 am UTC
Location: Scotland / Norway mainly

### Re: Four color theorem

You can do that with two colours. All the outer segments can be the same colour.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Four color theorem

Remember, touching at a point doesn't count.

The less silly version is:

Code: Select all

  +-------------+--------------+  |             |              |  |             |              |  |             +              |  |            / \             |  |           /   \            |  |          /     \           |  +---------+       +----------+  |          \     /           |  |           \   /            |  |            \ /             |  |             +              |  |             |              |  |             |              |  |             |              |  +-------------+--------------+

You coloured it in a particular pattern, like this:

Code: Select all

  +-------------+--------------+  |             |              |  |             |              |  | RED         +  GREEN       |  |            / \             |  |           /   \            |  |          /     \           |  +---------+       +----------+  |          \     /           |  |           \   /            |  |            \ /             |  |             +              |  | YELLOW      |  BLUE        |  |             |              |  |             |              |  +-------------+--------------+

Now, you say, what can the middle be? The problem here is that you are asking the wrong question.

The 4 colour theorem doesn't say "given any colouring of almost all of the plane, can you generate a colour for the holes". It requires mastery of the entire plane -- it gets to recolour what you have coloured to make things work.

In particular, you'll note that green and yellow, and red and blue, are not touching. So why are they different colours?

Absolutely no reason. Lets fix this:

Code: Select all

  +-------------+--------------+  |             |              |  |             |              |  | RED         +  GREEN       |  |            / \             |  |           /   \            |  |          /     \           |  +---------+       +----------+  |          \     /           |  |           \   /            |  |            \ /             |  |             +              |  | GREEN       |  RED         |  |             |              |  |             |              |  +-------------+--------------+

Now the middle can be coloured easily.

At this point, you might think about connecting the opposite green and red ones in such a way that they are forced to have distinct colours. But you'll see that it cannot be done.

Well, the proof says it cannot be done, more exactly.

Apparently, the five colour theorem proof is far easier than the four colour theorem proof. If I remember rightly, it reduces to taking something like the above (where the colours don't allow for another in the middle) and proving that there is a method to move colours around to free up a colour.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Four color theorem

Yakk wrote:Apparently, the five colour theorem proof is far easier than the four colour theorem proof. If I remember rightly, it reduces to taking something like the above (where the colours don't allow for another in the middle) and proving that there is a method to move colours around to free up a colour.

Pretty much. Here's a quick picture-free argument.

First, It is a trivial consequence of Euler's Formula that all planar graphs can be six-colored. Assume that there is some planar graph that cannot be five-colored, so that we may choose such a graph G that has a minimum number of vertices. G has some vertex v with degree of five or less. By minimality, G-v can be five-colored, so choose such a coloring and apply it to G. Since G cannot be five-colored, it must be that v has exactly five neighbors, and that they each have a different color***. Arbitrarily picking one of those neighbors and proceeding "clockwise" around v in our planar embedding, call those five colors 1, 2, 3, 4, and 5 and their corresponding vertices u1 through u5.

Now, consider the subgraph of G of all vertices with colors 1 and 3. If u1 and u3 are not in the same component, then we can show a five-coloring of the graph by switching all of the colors 1 and 3 in the component of the subgraph that contains u1, and then assigning color 1 to v. However, we have assumed that this is impossible, so u1 and u3 are connected in this subgraph, and therefore there is a path joining u1 to u3 that consists only of vertices labeled 1 and 3. Adding v to this path forms a cycle C in G; u2 is in the interior of this cycle and u4 is in the exterior. Now, consider the subgraph of all vertices with colors 2 and 4. Here, we know that u2 and u4 cannot be in the same component, because they are separated by a cycle which contains none of the vertices in the subgraph. Therefore, we may fulfill the program illustrated earlier in this paragraph to construct a five-coloring for G. Since we have assumed that to be impossible, our assumption that there is a planar graph that cannot be five-colored must have been erroneous. QED

Note: Novices look at this proof, observe that we didn't use u5 at all, and rush to conclude that this must be easily adaptable to a two-paragraph proof of 4CT. Such a proof is ungrounded because of the line that I marked ***. All we can say is that v has either four neighbors or five, and if there are five then the two neighbors that receive the same color are either "adjacent" (in the sense that they could be assigned vertices u1 and u2) or not (being, say, u1 and u3). Kempe's original proof of 4CT (which is around six paragraphs long) assumes that you can make this sort of "Kempe chain" argument for each of these three subcases, but the final case is sufficiently troublesome that the argument turns out to not work.

Moduli
Posts: 1
Joined: Wed Dec 05, 2012 9:30 am UTC

### Re: Four color theorem

I have also been studying the four color theorem. I have been reading Fritsch and Fritsch's The Four Color Theorem: History, Topological Foundations, and Idea of Proof. It has taken me some time to grasp all of the concepts outlined in the book, but I think I am beginning to get a feel for it. However, I believe I am missing some restriction on the types of maps that can be four-colored, since the map on the cover of the book seems to have no such four-coloring.
Could someone please explain this to me?

Sizik
Posts: 1261
Joined: Wed Aug 27, 2008 3:48 am UTC

### Re: Four color theorem

Moduli wrote:. . . the map on the cover of the book seems to have no such four-coloring.

Based on the picture here, color the bottom red segment blue, the green one directly above that red, and the center green.
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Four color theorem

Moduli wrote:I have also been studying the four color theorem. I have been reading Fritsch and Fritsch's The Four Color Theorem: History, Topological Foundations, and Idea of Proof. It has taken me some time to grasp all of the concepts outlined in the book, but I think I am beginning to get a feel for it. However, I believe I am missing some restriction on the types of maps that can be four-colored, since the map on the cover of the book seems to have no such four-coloring.
Could someone please explain this to me?

The restriction is just "planar 2d maps", where each region is contiguous.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

gmalivuk
GNU Terry Pratchett
Posts: 26836
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Four color theorem

Is it, though? I thought there were some mathematically possible regions fitting that condition which still do weird things.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Four color theorem

The theory of planar graphs is built on the Jordan curve theorem. So to the degree that you start describing curves that are self-intersecting or aren't continuous, all bets are off.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Four color theorem

This was published in scientific american as a counterexample a while back.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Four color theorem

jestingrabbit wrote:

This was published in scientific american as a counterexample a while back.

Your picture attachment went missing for some reason.
I'm sure you realise this, but I think it should be made explicit that
Spoiler:
that "counterexample" was an April Fool's joke by Martin Gardner.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Four color theorem

jaap wrote:
jestingrabbit wrote:
The attachment Color Madness Crop.jpg is no longer available

This was published in scientific american as a counterexample a while back.

Your picture attachment went missing for some reason.
I'm sure you realise this, but I think it should be made explicit that
Spoiler:
that "counterexample" was an April Fool's joke by Martin Gardner.

I'm not sure that your spoiler is right.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Four color theorem

jestingrabbit wrote:
jaap wrote:Your picture attachment went missing for some reason.
I'm sure you realise this, but I think it should be made explicit that
Spoiler:
that "counterexample" was an April Fool's joke by Martin Gardner.

I'm not sure that your spoiler is right.

Ah, sorry. That is a different thing than the one I thought you were referring to, which is the one mentioned on this mathworld page.

FancyHat
Posts: 341
Joined: Thu Oct 25, 2012 7:28 pm UTC

### Re: Four color theorem

I Googled, and found this on the Scientific American site: Color Madness [Preview]. There is one comment posted, rebutting the claim that six colours are required, and it does seem reasonable, though I haven't read the full article or the paper itself.

The second Google result was an old thread here, which, in turn, refers to a comment by the same commenter as above. Some comments later, t0rajir0u pointed out that the four colour problem is "a problem about a class of finite graphs called planar graphs, which are precisely the graphs (objects consisting of a set of vertices connected by a set of undirected edges) which can be drawn on a plane without the edges crossing." I gather this means the claimed counterexample doesn't qualify.
I am male, I am 'him'.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Four color theorem

The point was to refute Xanthir's claim that the theorem applies to all "planar 2d maps", where each region is contiguous." There's more to it than that.

In the example, the question of where the boundaries are is harder to decide than usual. Typically, the boundary of a region in the plane is the closure without the interior. Using this definition, all of the regions have an interval of the midline of the map in their boundary. If two regions share a boundary that isn't a finite union of points they need to have different colours. So, its a pretty good demonstration that there is pathological stuff around that you have to steer clear of.

One condition on maps that I believe works would be that it applies to all partitions of the plane where each set is borel and connected, and where all but a finite number of points on the plane there is an open neighborhood of the point that intersects only 2 regions.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

FancyHat
Posts: 341
Joined: Thu Oct 25, 2012 7:28 pm UTC

### Re: Four color theorem

jestingrabbit wrote:The point was to refute Xanthir's claim that the theorem applies to all "planar 2d maps", where each region is contiguous." There's more to it than that.

Okay, this stuff is beyond me, but I'm finding it interesting.
I am male, I am 'him'.

gmalivuk
GNU Terry Pratchett
Posts: 26836
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Four color theorem

Yeah, that's the one I was remembering when I posted.

The actual theorem, I believe, was proved in terms of planar graphs with no crossing edges, where each point on the graph corresponds to a region in a "non-pathological" map and each edge in the graph corresponds to the border two regions share. The "counterexample" image you posted does not have such a corresponding graph, so it isn't a counterexample to the proved version of the theorem, but is a counterexample to a naive interpretation thereof.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

### Re: Four color theorem

Also, the usual statement is along the lines of "regions that touch at a corner may have the same color". If you define a corner as "a point which is in the closure of more than two regions", then I believe all the wacky counter-examples are now fine again (so the pathological region where all four countries are closer and closer together limit to a "corner" which is really a line segment). Not the best definition of corner, really, but it's the approach Wikipedia takes.