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

Postby mike-l » Wed Mar 24, 2010 3:09 pm UTC

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.

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

Re: Four color theorem

Postby skeptical scientist » Wed Mar 24, 2010 3:20 pm UTC

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. :P
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

Postby mike-l » Wed Mar 24, 2010 3:28 pm UTC

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. :P

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

Postby Suffusion of Yellow » Wed Mar 24, 2010 7:55 pm UTC

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

Postby mike-l » Wed Mar 24, 2010 7:57 pm UTC

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.

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

Re: Four color theorem

Postby BlackSails » Wed Mar 24, 2010 9:44 pm UTC

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

Postby supremum » Wed Mar 24, 2010 10:45 pm UTC

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

Postby Tirian » Thu Mar 25, 2010 1:14 am UTC

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

Postby achan1058 » Thu Mar 25, 2010 1:46 am UTC

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

Postby DavCrav » Thu Mar 25, 2010 2:31 pm UTC

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

Postby Fume Troll » Thu Mar 25, 2010 2:39 pm UTC

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

Postby mike-l » Thu Mar 25, 2010 2:49 pm UTC

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.

User avatar
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

Postby Yakk » Thu Mar 25, 2010 4:03 pm UTC

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.

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

Re: Four color theorem

Postby gmalivuk » Thu Mar 25, 2010 5:08 pm UTC

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

Postby Fume Troll » Wed Apr 07, 2010 2:11 pm UTC


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

Re: Four color theorem

Postby DavCrav » Wed Apr 07, 2010 5:33 pm UTC

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.

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

Re: Four color theorem

Postby phlip » Thu Apr 08, 2010 11:19 am UTC


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]

User avatar
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

Postby jestingrabbit » Thu Apr 08, 2010 11:38 am UTC

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

Postby Fume Troll » Thu Apr 08, 2010 11:49 am UTC

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.

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

Re: Four color theorem

Postby gmalivuk » Thu Apr 08, 2010 11:52 am UTC

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

Postby bojanglin » Thu May 06, 2010 1:44 am UTC

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
Lydianasia.jpg

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

Re: Four color theorem

Postby BlackSails » Thu May 06, 2010 1:55 am UTC

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

Postby bojanglin » Thu May 06, 2010 2:06 am UTC

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

Postby Fume Troll » Thu May 06, 2010 1:11 pm UTC

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

User avatar
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

Postby Yakk » Thu May 06, 2010 2:22 pm UTC

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

Postby Tirian » Thu May 06, 2010 7:07 pm UTC

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

Postby Moduli » Wed Dec 05, 2012 9:36 am UTC

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?

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

Re: Four color theorem

Postby Sizik » Wed Dec 05, 2012 6:31 pm UTC

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.

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Four color theorem

Postby Xanthir » Fri Dec 07, 2012 10:04 pm UTC

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)))

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

Re: Four color theorem

Postby gmalivuk » Sun Dec 09, 2012 5:31 am UTC

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

Postby Tirian » Sun Dec 09, 2012 6:02 am UTC

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.

User avatar
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

Postby jestingrabbit » Sun Dec 09, 2012 6:54 am UTC

Color Madness Crop.jpg


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

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

Re: Four color theorem

Postby jaap » Sun Dec 09, 2012 7:13 am UTC

jestingrabbit wrote:
Color Madness Crop.jpg


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.

User avatar
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

Postby jestingrabbit » Sun Dec 09, 2012 7:22 am UTC

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.

I was talking about this thing

Color Madness Crop.jpg
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Four color theorem

Postby jaap » Sun Dec 09, 2012 7:29 am UTC

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.
I was talking about this thing


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

Postby FancyHat » Sun Dec 09, 2012 8:23 am UTC

jestingrabbit wrote:I was talking about this thing

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'.

User avatar
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

Postby jestingrabbit » Sun Dec 09, 2012 8:54 am UTC

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

Postby FancyHat » Sun Dec 09, 2012 9:23 am UTC

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'.

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

Re: Four color theorem

Postby gmalivuk » Sun Dec 09, 2012 5:41 pm UTC

jestingrabbit wrote:I was talking about this thing
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

Postby letterX » Sun Dec 09, 2012 8:07 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests