Four color theorem
Moderators: gmalivuk, Moderators General, Prelates
Four color theorem
So, I was reading about the 4 color theorem on wikipedia (http://en.wikipedia.org/wiki/Four_color_theorem).
Now, perhaps there's something about the theorem's assumptions that I don't understand, but there seems to be to be a very obvious counter example.
Imagine a map like this:
http://www.education.com/files/74201_74300/74231/file_74231.jpg
but with a circle in the middle. The circle has a boundary with all four other regions of the map (in fact, you can draw lines from the border of the circle to the border of the large circle to create any number of regions that border the circle).
Putting this into the "planar graph" described at the bottom of "Precise formulation of the theorem" would be an X, with a point at the end of each segment and one where they cross. We can then add any number of lines from the middle to other points.
Is there something I'm missing.
Now, perhaps there's something about the theorem's assumptions that I don't understand, but there seems to be to be a very obvious counter example.
Imagine a map like this:
http://www.education.com/files/74201_74300/74231/file_74231.jpg
but with a circle in the middle. The circle has a boundary with all four other regions of the map (in fact, you can draw lines from the border of the circle to the border of the large circle to create any number of regions that border the circle).
Putting this into the "planar graph" described at the bottom of "Precise formulation of the theorem" would be an X, with a point at the end of each segment and one where they cross. We can then add any number of lines from the middle to other points.
Is there something I'm missing.
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Four color theorem
The regions that border the circle dont border each other, so many of them will be the same color.
Re: Four color theorem
BlackSails wrote:The regions that border the circle dont border each other, so many of them will be the same color.
Right, but the circle will still border all 4 others, so if the surrounding regions are colors A, B, C, and D, the circle would have to be a 5th color E to not be the same as one of the regions it borders.
 Torn Apart By Dingos
 Posts: 817
 Joined: Thu Aug 03, 2006 2:27 am UTC
Re: Four color theorem
The surrounding ones don't have to be different colors. They can be colored A,B,A,C.
The innermost five parts of the following diagram is the same as your example, and it's colored with four colors.
The innermost five parts of the following diagram is the same as your example, and it's colored with four colors.
 Yakk
 Poster with most posts but no title.
 Posts: 11128
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Four color theorem
Code: Select all
/+\
  
  
  
 A + B 
 / \ 
 / \ 
 / \ 
++ C ++
 \ / 
 \ / 
 \ / 
 + 
 B  A 
  
  
\+/
In short: no, you cannot provide a graph that cannot be 4coloured.
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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 135
 Joined: Sat Nov 15, 2008 3:47 am UTC
Re: Four color theorem
That can't possibly be true, as the following counterexample has been published by Gardner in Scientific American
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Four color theorem
Seriously? He published that? It's pretty funny, I guess, but not really very hard, since it took me about 15 minutes with photoshop to get a 4coloring, and it didn't even require much backtracking. (Unless I've missed something somewhere?)
P.S. I notice that your map differs slightly from the one on http://mathworld.wolfram.com/FourColorTheorem.html. What's up with that?
Spoiler:
P.S. I notice that your map differs slightly from the one on http://mathworld.wolfram.com/FourColorTheorem.html. What's up with that?
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
"With math, all things are possible." —Rebecca Watson
Re: Four color theorem
It was from the April 1975 issue of Sci Am, so you can guess where he was going. He also reported that [imath]e^{\pi\sqrt{163}}[/imath] is an integer and provided a simple thought experiment disproving special relativity, among quite a few other things.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26766
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Four color theorem
Tirian wrote:He also reported that [imath]e^{\pi\sqrt{163}}[/imath] is an integer
That is an impressive string of 9's after the decimal point, though. I guess the problem is just that fitting [imath]e^{\pi\sqrt{163}} 262537412640768743[/imath] into a comic takes too much space.
Re: Four color theorem
gmalivuk wrote:Tirian wrote:He also reported that [imath]e^{\pi\sqrt{163}}[/imath] is an integer
That is an impressive string of 9's after the decimal point, though.
That's Srinivasa Ramanujan for you.
Re: Four color theorem
The following is a "counterexample" of the fourcolor theorem I received in my Combinatorics class (M.S. Applied Math program, taken @ JHUAPL, 2008). It states that if an infinitely decreasing segment is snaked down asymptotically to a middle boundary, that the map will require six colors to ensure no two regions will have the same color and touch.
I disagreed and told my professor so. He agreed with me that this may not be a counterexample and to send it in to SciAm to confirm. I haven't heard anything in two years... Oh, well.
The numbered regions (I numbered them 16, after their colors) meet at the top, bottom, and sides of the graphic, forcing 1, 2, and 3 to be different colors. Similarly, 4, 5, and 6 must also be different colors.
My arguments were as follows:
1) That 2 & 4 never meet, nor do 1 & 5, since 3 & 6 will always be between them, regardless of how far "down the rabbit hole" you go, which allows them to be the same color. Also, 3 & 6 are allowed to be the same color, as they will "meet" at some infinitely distant abstract point, precluding the option for them ever to meet.
2) If it is the author's point that we could conclude that "infinity" is a destination that will inexorably lead to two of the regions meeting at a limit point, we have several options:
If 1 & 5 meet at infinity, then it will also follow that neither 3 & 6, nor 2 & 4 can meet, allowing them to be the same colors; 4CT holds.
If 3 & 6 meet, it follows that neither 1 & 5, nor 2 & 4 may meet.
If 2 & 4 meet, it follows that neither 1 & 5, nor 3 & 6 may meet.
I stated that regardless of which avenue was chosen, only four colors are needed.
The only way I could imagine that Hudson (Western Washington U) was correct, at first, was that he must be arguing a quantum mechanical approach: since we cannot determine which of the above cases is true, we must hold all of them as potentially true until more information is given.
The point of the article was actually given in terms of neighborhoods (real analysis). Any neighborhood chosen around the border region will contain all six regions, regardless of how small the neighborhood is.
I still claim that it is inaccurate, as the regions will never meet... How about you?
I disagreed and told my professor so. He agreed with me that this may not be a counterexample and to send it in to SciAm to confirm. I haven't heard anything in two years... Oh, well.
The numbered regions (I numbered them 16, after their colors) meet at the top, bottom, and sides of the graphic, forcing 1, 2, and 3 to be different colors. Similarly, 4, 5, and 6 must also be different colors.
My arguments were as follows:
1) That 2 & 4 never meet, nor do 1 & 5, since 3 & 6 will always be between them, regardless of how far "down the rabbit hole" you go, which allows them to be the same color. Also, 3 & 6 are allowed to be the same color, as they will "meet" at some infinitely distant abstract point, precluding the option for them ever to meet.
2) If it is the author's point that we could conclude that "infinity" is a destination that will inexorably lead to two of the regions meeting at a limit point, we have several options:
If 1 & 5 meet at infinity, then it will also follow that neither 3 & 6, nor 2 & 4 can meet, allowing them to be the same colors; 4CT holds.
If 3 & 6 meet, it follows that neither 1 & 5, nor 2 & 4 may meet.
If 2 & 4 meet, it follows that neither 1 & 5, nor 3 & 6 may meet.
I stated that regardless of which avenue was chosen, only four colors are needed.
The only way I could imagine that Hudson (Western Washington U) was correct, at first, was that he must be arguing a quantum mechanical approach: since we cannot determine which of the above cases is true, we must hold all of them as potentially true until more information is given.
The point of the article was actually given in terms of neighborhoods (real analysis). Any neighborhood chosen around the border region will contain all six regions, regardless of how small the neighborhood is.
I still claim that it is inaccurate, as the regions will never meet... How about you?
"We never do anything well unless we love doing it for its own sake."
Avatar: I made a "plastic carrier" for Towel Day à la So Long and Thanks for All the Fish.
Avatar: I made a "plastic carrier" for Towel Day à la So Long and Thanks for All the Fish.
Re: Four color theorem
I'm on your side. If someone wanted to convince me that regions 2 and 4 are adjacent, then they'd have to construct a continuous function f from [0,1] into the map where f(0) was in region 2, f(1) was in region 4, and the entire range of the function was in the union of regions 2 and 4. I don't see that happening, so they could safely receive the same color. I'm a little too tired to fight through the topology, but the map might actually be 3colorable.
The hypothesis that our understanding of quantum mechanics applies to the Euclidean plane is precious.
The hypothesis that our understanding of quantum mechanics applies to the Euclidean plane is precious.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26766
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Four color theorem
It comes down to how you precisely define "touching". Once you do that, we can address whether that is actually a counterexample. But if it requires sharing a border, where a point on the border is defined as one for which every neighborhood contains points of both sets, then I'm afraid this would be a kind of counterexample.
 silverhammermba
 Posts: 178
 Joined: Fri Oct 13, 2006 1:16 am UTC
Re: Four color theorem
This is a good example of how counterintuitive the four color theorem can be.
For a good laugh, check out this thread http://www.facepunch.com/showthread.php?t=699974
It's 14 solid pages of people trying to disprove a variant of the four color theorem.
For a good laugh, check out this thread http://www.facepunch.com/showthread.php?t=699974
It's 14 solid pages of people trying to disprove a variant of the four color theorem.
 phlip
 Restorer of Worlds
 Posts: 7572
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Four color theorem
Tirian wrote:If someone wanted to convince me that regions 2 and 4 are adjacent, then they'd have to construct a continuous function f from [0,1] into the map where f(0) was in region 2, f(1) was in region 4, and the entire range of the function was in the union of regions 2 and 4.
I don't think that's a good enough definition... consider a circle split up into a number of sectors... between any two sectors you can draw a line from a point in there, to the centre, and then to the other sector. So all of them would be adjacent. Or, in general, any two regions that touch only on their corner (which aren't considered adjacent for the 4colour problem).
We need some definition of a boundary to exclude single points... and also some definition of a region that excludes simple lines. For instance, say:
Code: Select all
++
 
++ A ++
 ++ 
 B B 
 ++ 
++ C ++
 
++
We can simply declare the regions to be open sets, which would fix my example, but wouldn't be enough for andrew's puzzle... even defining that with open sets, the middle interval of the line that separates the two halves (ie the bit where regions 2 and 5 "meet") is still a boundary of all 6 regions. But what makes it feel "wrong" to me is that that interval is still just a simple line... if you consider the closure of, say, region 2, then it's a solid block of wibbly region, and then a single line along the middle of the map, which isn't even pathconnected to the rest of the region.
How'sabout: the regions are a bunch of disjoint open pathconnected sets. The kindaclosure of a set S is the set of points x where x is in the closure of S, and [imath]S \cup \{x\}[/imath] is pathconnected. Two regions are adjacent if their kindaclosures intersect, and that intersection contains a nonzerolength curve (not just a single point).
That seems to fit what the English description of the puzzle is doing. Though, really, the English description of the puzzle implies that all this infinitesimal fiddly bollocks isn't allowed at all, all the regions have finite perimeter, that sort of thing...
That solves andrew's puzzle at least, since now that contentious interval in the middle is in the kindaclosure of none of the sets, rather than all of them (and we get that each of the regions are adjacent to only the 2 that you'd intuitively expect). But maybe it's too conservative, and would throw out other regions that really should be considered adjacent?
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Four color theorem
The definitions relevant to the fourcolor theorem are entirely combinatorial. It's 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. The vertices represent the countries and the edges represent the places at which the countries border each other. This definition is totally unambiguous. In fact, the fourcolor theorem can be rephrased as the statement that the chromatic polynomial of a planar graph, which can be explicitly evaluated using a certain recurrence, takes a positive value at 4.
Last edited by t0rajir0u on Tue Mar 16, 2010 6:44 am UTC, edited 2 times in total.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Four color theorem
I'm with torajirou. Just formalize it as graphs, and the whole issue disappears. Any reasonable map is going to be equivalent to a planar graph, and we don't have to worry too carefully about a precise definition of a "reasonable" map as opposed to an unreasonable one.
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
"With math, all things are possible." —Rebecca Watson
 phlip
 Restorer of Worlds
 Posts: 7572
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Four color theorem
Sure, going with graphs is the best way, and the easiest way to make a unambiguous definition of the puzzle.
It doesn't really answer the question of what makes an "unreasonable" map, though. I mean, it's all very well to go back to andrew's puzzle and say "that's not a reasonable map, 'cause its dual is K_{6}, and that isn't planar"... but that's not really an answer... the question still stands as to what exactly is unreasonable about it.
However, in looking up "dual" on WP to make sure that was the right word to use... I figured out a definition that I actually wanted to use while I was writing my previous post, but I couldn't think of a decent way to word it  the important part when you're looking at the map isn't the regions themselves, but their boundaries. And for a "reasonable" map, those boundaries will be a bunch of lines connecting various intersecting points  that is, a graph. The dual of that graph would then be the graph that you have to find a 4colouring of.
And if you try to find a graph which traces the boundaries of andrew's map, you get:(the W's represent pointlessly wibbly lines). Any way you connect the lines up at that question mark (either connect them all at the same point, or have several points there with some complicated connections) you'll end up with a map that satisfies the 4colouring theorem.
It doesn't really answer the question of what makes an "unreasonable" map, though. I mean, it's all very well to go back to andrew's puzzle and say "that's not a reasonable map, 'cause its dual is K_{6}, and that isn't planar"... but that's not really an answer... the question still stands as to what exactly is unreasonable about it.
However, in looking up "dual" on WP to make sure that was the right word to use... I figured out a definition that I actually wanted to use while I was writing my previous post, but I couldn't think of a decent way to word it  the important part when you're looking at the map isn't the regions themselves, but their boundaries. And for a "reasonable" map, those boundaries will be a bunch of lines connecting various intersecting points  that is, a graph. The dual of that graph would then be the graph that you have to find a 4colouring of.
And if you try to find a graph which traces the boundaries of andrew's map, you get:
Code: Select all
+++
  
 +WWWWW\  /WWWWW+ 
  \/  
++ ? ++
  /\  
 +WWWWW/  \WWWWW+ 
  
+++
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Four color theorem
phlip wrote:Sure, going with graphs is the best way, and the easiest way to make a unambiguous definition of the puzzle.
It doesn't really answer the question of what makes an "unreasonable" map, though. I mean, it's all very well to go back to andrew's puzzle and say "that's not a reasonable map, 'cause its dual is K_{6}, and that isn't planar"... but that's not really an answer... the question still stands as to what exactly is unreasonable about it.
One reasonable attempt at a definition is that borders should be simple closed curves, and countries should be their interiors. But the whole point of formalizing it as a graph is that you don't have to worry about which particular partitions of the plane are valid maps, and which are unreasonable. And when it comes down to it, the original inspiration to the problem was actual maps, not arbitrary partitions of the plane, so phrasing it in the language of graphs is no more of a stretch than partitions of the plane.
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
"With math, all things are possible." —Rebecca Watson
Re: Four color theorem
silverhammermba wrote:This is a good example of how counterintuitive the four color theorem can be.
For a good laugh, check out this thread http://www.facepunch.com/showthread.php?t=699974
It's 14 solid pages of people trying to disprove a variant of the four color theorem.
It looks to me like they are trying to find a planar embedding of K_{5}, which is not possible because of the 4color theorem among other things, but is not equivalent to it. Funny to read nonetheless.
Edit: My favorite post so far:
It's impossible. It's a really simple proof if you think about it.
Theory:
You can only do as many colors as D*2, D = dimension where D > 1
Proof:
If you try doing 3 colored lines in 1D it won't work, but 2 works
If you try doing it with 7colored cubes/polygons in 3D it won't work, but 6 works
Edit2: Even better
Einstein has proven the impossibility of this task a thousand years ago.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
Re: Four color theorem
phlip wrote:Sure, going with graphs is the best way, and the easiest way to make a unambiguous definition of the puzzle.
It doesn't really answer the question of what makes an "unreasonable" map, though. I mean, it's all very well to go back to andrew's puzzle and say "that's not a reasonable map, 'cause its dual is K_{6}, and that isn't planar"... but that's not really an answer... the question still stands as to what exactly is unreasonable about it.
Except that the version of the theorem that has been proved was stated in terms of graph theory. So if you want to talk about other arbitrary partitions of the plane that don't correspond to planar graphs, that might be an interesting problem but it is NOT equivalent to or even related to the FourColor Theorem.
 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
Given that the theorem was conjectured after observations when colouring a map, which was in some sense a partition of (a subset of) the plane, I think its more than a little hyperbolic to say that its not related to the four colour theorem.
And having brought up hyperbolic stuff, I'm reminded of the elaborate defintions that are out there for fundamental domains of Fuchsian groups. I expect that examining those sort of definitions is exactly what's required to end up with a good set of definitions here. They're ridiculously elaborate, but all the conditions are necessary it seemed to me when I was studying it, though what they were escapes me more than a decade later.
Of course, we could just say that a map whose adjacency graph is planar is okay, but that's kinda begging the question.
And having brought up hyperbolic stuff, I'm reminded of the elaborate defintions that are out there for fundamental domains of Fuchsian groups. I expect that examining those sort of definitions is exactly what's required to end up with a good set of definitions here. They're ridiculously elaborate, but all the conditions are necessary it seemed to me when I was studying it, though what they were escapes me more than a decade later.
Of course, we could just say that a map whose adjacency graph is planar is okay, but that's kinda begging the question.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 76
 Joined: Wed Dec 23, 2009 11:11 am UTC
 Location: London, UK
 Contact:
Re: Four color theorem
I remember reading a book when I was young called The Laws Of Form where the author showed  or claimed to show  a proof for the four colour theorm using his odd notation. Anyone else seen this ? I was young and didn't understand and the book had slight overtones of metaphysics and whatnot so I didn't take it too seriously.
Ah, here: http://www.amazon.com/LawsFormSpencer ... ap_title_1
Ah, here: http://www.amazon.com/LawsFormSpencer ... ap_title_1
Re: Four color theorem
phlip wrote:It doesn't really answer the question of what makes an "unreasonable" map, though.
Yes, it does: an unreasonable map is one that can't be represented by a finite planar graph. If you prefer to talk about actual subsets of the plane that may not necessarily be captured by this formalism, then you are no longer talking about the fourcolor theorem.
 Yakk
 Poster with most posts but no title.
 Posts: 11128
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Four color theorem
As far as I know, the only successful proof of the four color theorem required a huge database of "special cases" to be manually checked. So I doubt that proof you are talking about is a good one.
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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 42
 Joined: Thu Jan 01, 2009 6:15 pm UTC
Re: Four color theorem
Yakk wrote:As far as I know, the only successful proof of the four color theorem required a huge database of "special cases" to be manually checked. So I doubt that proof you are talking about is a good one.
This is true, I'm writing my senior research paper on it
 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
There were quite a few tries that failed though. It could easily be a version of one of those.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Four color theorem
Ken Appel (one of the coauthors) works at UNH in Durham, NH. He came in to our Math History class and gave a lecture on the fourcolor theorem. Had I known about this counterexample, I would have asked him about his thoughts on infinite maps... Come to think of it, where's his email... Have it somewhere.
"We never do anything well unless we love doing it for its own sake."
Avatar: I made a "plastic carrier" for Towel Day à la So Long and Thanks for All the Fish.
Avatar: I made a "plastic carrier" for Towel Day à la So Long and Thanks for All the Fish.
 silverhammermba
 Posts: 178
 Joined: Fri Oct 13, 2006 1:16 am UTC
Re: Four color theorem
mikel wrote:silverhammermba wrote:This is a good example of how counterintuitive the four color theorem can be.
For a good laugh, check out this thread http://www.facepunch.com/showthread.php?t=699974
It's 14 solid pages of people trying to disprove a variant of the four color theorem.
It looks to me like they are trying to find a planar embedding of K_{5}, which is not possible because of the 4color theorem among other things, but is not equivalent to it. Funny to read nonetheless.
Alright, not equivalent. But they're basically trying to find a counterexample to a proven theory.
Re: Four color theorem
That's not so wild. The Kempe "proof" of 4CT took eleven years to debunk, and it only had about four cases.
Re: Four color theorem
Yeah, aren't there hundreds (thousands?) of cases that a computer verified for the proof? It's an accepted proof but isn't it possible that something went wrong that we haven't found yet?
double epsilon = .0000001;
 BlackSails
 Posts: 5315
 Joined: Thu Dec 20, 2007 5:48 am UTC
Re: Four color theorem
Dason wrote:Yeah, aren't there hundreds (thousands?) of cases that a Pornography Storage Apparatus verified for the proof? It's an accepted proof but isn't it possible that something went wrong that we haven't found yet?
Isnt that true of every proof?
Re: Four color theorem
BlackSails wrote:Dason wrote:Yeah, aren't there hundreds (thousands?) of cases that a Pornography Storage Apparatus verified for the proof? It's an accepted proof but isn't it possible that something went wrong that we haven't found yet?
Isnt that true of every proof?
I guess I was more or less referring to the computer generated portion of the proof... Gogowikipedia...
Initially, their proof was not accepted by all mathematicians because the computerassisted proof was infeasible for a human to check by hand (Swart 1980). Since then the proof has gained wider acceptance, although doubts remain (Wilson 2002, 216–222).
double epsilon = .0000001;

 Posts: 42
 Joined: Thu Jan 01, 2009 6:15 pm UTC
Re: Four color theorem
BlackSails wrote:Dason wrote:Yeah, aren't there hundreds (thousands?) of cases that a Pornography Storage Apparatus verified for the proof? It's an accepted proof but isn't it possible that something went wrong that we haven't found yet?
Isnt that true of every proof?
Not to this degree

 Posts: 135
 Joined: Fri Aug 29, 2008 9:25 pm UTC
Re: Four color theorem
Suffusion of Yellow wrote:BlackSails wrote:Dason wrote:Yeah, aren't there hundreds (thousands?) of cases that a Pornography Storage Apparatus verified for the proof? It's an accepted proof but isn't it possible that something went wrong that we haven't found yet?
Isnt that true of every proof?
Not to this degree
I don't know about that; what is the longest mathematical proof anyone can name? Given that we're not exactly computerlike in our algorithmfollowing abilities, I suspect it wouldn't take a proof involving hundreds of thousand of individual cases checked to reach a level of human unreliability well beyond that for a software program which checks hundreds of thousands of cases.
Also  establishing the optimal solution to any relatively large integer programming problem seems perfectly analogous to this situation. Would you also claim that an integer programming problem solved by branchandbound or whatever optimization algorithm is, at algorithm's end, not prooflike in its reliability?
...she reminds you of the invisible form of the soul; she gives life to her own discoveries; she awakens the mind and purifies the intellect; she brings light to our intrinsic ideas; she abolishes oblivion and ignorance which are ours by birth...
 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
Dason wrote:Yeah, aren't there hundreds (thousands?) of cases that a Pornography Storage Apparatus verified for the proof? It's an accepted proof but isn't it possible that something went wrong that we haven't found yet?
There were more than a thousand initially, but there are only about 633 now. If someone wanted to, they could check one graph every day and get it done in a couple of years. But the machines have done it for us, so why bother with it?
RabidAltruism wrote:I don't know about that; what is the longest mathematical proof anyone can name? Given that we're not exactly Pornography Storage Apparatuslike in our algorithmfollowing abilities, I suspect it wouldn't take a proof involving hundreds of thousand of individual cases checked to reach a level of monkeigh unreliability well beyond that for a software program which checks hundreds of thousands of cases.
ALSO YOU GUYS:  establishing the optimal solution to any relatively large integer programming problem seems perfectly analogous to this situation. Would you ALSO YOU GUYS: claim that an integer programming problem solved by branchandbound or whatever optimization algorithm is, at algorithm's end, not prooflike in its reliability?
Two proofs that come to mind are the proof that the 36 officers problem doesn't have a solution, and the categorisation of finite simple groups. The first was an inelegant case bash of a big problem (you can probably programme something to check it in a few minutes on your home computer, but its big for a human) and the second is incredibly gigantic and mindbendingly complicated. It wasn't computer aided, and it would be hard to make a machine check it.
I personally am convinced that all these results are correct, that the proofs of the four colour and 36 officers problems are correct, and the broad strokes of the categorisation are correct, though I don't think it impossible that there may be errors in the details.
Ultimately, no one is forcing anyone to believe that these proofs are persuasive or logically correct, but they have, at various times, come under a great deal of scrutiny, and have withstood it with little alteration. That's a pretty good reason to believe that they are correct imo.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 42
 Joined: Thu Jan 01, 2009 6:15 pm UTC
Re: Four color theorem
RabidAltruism wrote:I don't know about that; what is the longest mathematical proof anyone can name?
Classification of finite sets, its 1500+ pages, but each part of the proof has been checked and verified....just not by the same person, as opposed to 4 Color Theorem.
I don't think it likely 4 color theorem's proofs are wrong, computer proofs by exhaustion are just so...eh. not why i like math.
Re: Four color theorem
jestingrabbit wrote:Two proofs that come to mind are ... and the categorisation of finite simple groups. ... the second is incredibly gigantic and mindbendingly complicated. It wasn't Pornography Storage Apparatus aided, and it would be hard to make a machine check it.
I should point out that the original classification of finite simple groups does require a computer, namely for the construction of the sporadic simple groups. I believe it is only recently that computerfree constructions of every one of these groups have been found, which pleases certain important mathematicians who have entrenched opinions about computers, naming no names.
There also was a sizeable gap in the classification, which people knew about at the time but kind of ignored, until Aschbacher and Smith completed the classification of the socalled quasithin simple groups. This was done at around 2000.
There was also the RobertsonSeymour theorem on excluded minors; something like 500 pages, so quite long for an individual theorem.
Suffusion of Yellow wrote:Classification of finite sets, its [sic] 1500+ pages...
??? I have no idea what this is.
Re: Four color theorem
Classification of finite sets is a very difficult and untractable problem, unlike finite groups which took a mere 1500 pages.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Four color theorem
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.
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
"With math, all things are possible." —Rebecca Watson
Who is online
Users browsing this forum: No registered users and 6 guests