Four color theorem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

pizzazz
Posts: 487
Joined: Fri Mar 12, 2010 4:44 pm UTC

Four color theorem

Postby pizzazz » Fri Mar 12, 2010 5:04 pm UTC

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.

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

Re: Four color theorem

Postby BlackSails » Fri Mar 12, 2010 5:08 pm UTC

The regions that border the circle dont border each other, so many of them will be the same color.

pizzazz
Posts: 487
Joined: Fri Mar 12, 2010 4:44 pm UTC

Re: Four color theorem

Postby pizzazz » Fri Mar 12, 2010 5:19 pm UTC

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.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Four color theorem

Postby Torn Apart By Dingos » Fri Mar 12, 2010 5:22 pm UTC

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.

Image

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 » Fri Mar 12, 2010 5:34 pm UTC

Code: Select all

    /-----------+-----------\
    |           |           |
    |           |           |
    |           |           |
    |    A      +      B    |
    |          / \          |
    |         /   \         |
    |        /     \        |
    +-------+   C   +-------+
    |        \     /        |
    |         \   /         |
    |          \ /          |
    |           +           |
    |    B      |      A    |
    |           |           |
    |           |           |
    \-----------+-----------/


In short: no, you cannot provide a graph that cannot be 4-coloured. :)
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.

dean.menezes
Posts: 135
Joined: Sat Nov 15, 2008 3:47 am UTC

Re: Four color theorem

Postby dean.menezes » Sat Mar 13, 2010 3:06 am UTC

That can't possibly be true, as the following counterexample has been published by Gardner in Scientific American ;)

Image

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 » Sat Mar 13, 2010 3:35 am UTC

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 4-coloring, and it didn't even require much backtracking. (Unless I've missed something somewhere?)
Spoiler:
Untitled-1 copy.gif
Untitled-1 copy.gif (9.33 KiB) Viewed 13987 times


My basic strategy was to three color large areas of the map in order to have many degrees of freedom that I could later use to twerk problematic regions.


P.S. I notice that your map differs slightly from the one on http://mathworld.wolfram.com/Four-ColorTheorem.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

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

Re: Four color theorem

Postby Tirian » Sat Mar 13, 2010 1:25 pm UTC

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.

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

Re: Four color theorem

Postby gmalivuk » Sat Mar 13, 2010 3:02 pm UTC

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.
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 » Sat Mar 13, 2010 5:37 pm UTC

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.

User avatar
andrewxc
Posts: 223
Joined: Tue Sep 09, 2008 2:39 am UTC
Location: Savage, MD

Re: Four color theorem

Postby andrewxc » Tue Mar 16, 2010 3:14 am UTC

The following is a "counter-example" of the four-color 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.
Color Madness Crop.jpg
Graphic from SciAm, Jan 2003 - Fair Use Act applies.


I disagreed and told my professor so. He agreed with me that this may not be a counter-example 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 1-6, 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.

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

Re: Four color theorem

Postby Tirian » Tue Mar 16, 2010 3:30 am UTC

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 3-colorable.

The hypothesis that our understanding of quantum mechanics applies to the Euclidean plane is precious.

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

Re: Four color theorem

Postby gmalivuk » Tue Mar 16, 2010 4:50 am UTC

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

User avatar
silverhammermba
Posts: 178
Joined: Fri Oct 13, 2006 1:16 am UTC

Re: Four color theorem

Postby silverhammermba » Tue Mar 16, 2010 5:05 am UTC

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.

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 » Tue Mar 16, 2010 5:41 am UTC

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 4-colour 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  +---+
    |     |
    +-----+
and take the limit as the gap between A and C reaches zero... but the two regions of B are still connected by a line "between" A and C. Then A is, really, now adjacent to C, but both are adjacent to B (which is still one region, despite being on both sides of A and C, because of the line connecting it). It's pretty easy to extend this to break 4CT.

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 path-connected to the rest of the region.

How'sabout: the regions are a bunch of disjoint open path-connected sets. The kinda-closure 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 path-connected. Two regions are adjacent if their kinda-closures intersect, and that intersection contains a non-zero-length 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 kinda-closure 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)⚠);}
[he/him/his]

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Four color theorem

Postby t0rajir0u » Tue Mar 16, 2010 5:46 am UTC

The definitions relevant to the four-color 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 four-color 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.

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 » Tue Mar 16, 2010 6:38 am UTC

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

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 » Tue Mar 16, 2010 7:47 am UTC

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 K6, 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 4-colouring 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+  |
|          |          |
+----------+----------+
(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 4-colouring theorem.

Code: Select all

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

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 » Tue Mar 16, 2010 11:07 am UTC

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 K6, 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

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

Re: Four color theorem

Postby mike-l » Tue Mar 16, 2010 2:19 pm UTC

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 K5, which is not possible because of the 4-color 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.

davegabis
Posts: 12
Joined: Thu Feb 25, 2010 1:59 pm UTC

Re: Four color theorem

Postby davegabis » Tue Mar 16, 2010 2:44 pm UTC

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 K6, 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 Four-Color Theorem.

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 » Tue Mar 16, 2010 3:43 pm UTC

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Peter Galbavy
Posts: 76
Joined: Wed Dec 23, 2009 11:11 am UTC
Location: London, UK
Contact:

Re: Four color theorem

Postby Peter Galbavy » Tue Mar 16, 2010 4:37 pm UTC

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 what-not so I didn't take it too seriously.

Ah, here: http://www.amazon.com/Laws-Form-Spencer ... ap_title_1

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Four color theorem

Postby t0rajir0u » Tue Mar 16, 2010 4:42 pm UTC

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 four-color theorem.

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 » Tue Mar 16, 2010 4:44 pm UTC

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.

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

Re: Four color theorem

Postby Suffusion of Yellow » Fri Mar 19, 2010 12:19 am UTC

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

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 » Fri Mar 19, 2010 12:27 am UTC

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.

User avatar
andrewxc
Posts: 223
Joined: Tue Sep 09, 2008 2:39 am UTC
Location: Savage, MD

Re: Four color theorem

Postby andrewxc » Fri Mar 19, 2010 11:22 am UTC

Ken Appel (one of the co-authors) works at UNH in Durham, NH. He came in to our Math History class and gave a lecture on the four-color theorem. Had I known about this counter-example, 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.

User avatar
silverhammermba
Posts: 178
Joined: Fri Oct 13, 2006 1:16 am UTC

Re: Four color theorem

Postby silverhammermba » Tue Mar 23, 2010 3:46 pm UTC

mike-l 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 K5, which is not possible because of the 4-color 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.

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

Re: Four color theorem

Postby Tirian » Tue Mar 23, 2010 4:41 pm UTC

That's not so wild. The Kempe "proof" of 4CT took eleven years to debunk, and it only had about four cases.

User avatar
Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Four color theorem

Postby Dason » Tue Mar 23, 2010 4:46 pm UTC

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;

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

Re: Four color theorem

Postby BlackSails » Tue Mar 23, 2010 10:03 pm UTC

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?

User avatar
Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

Re: Four color theorem

Postby Dason » Tue Mar 23, 2010 10:06 pm UTC

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... Go-go-wikipedia...
Initially, their proof was not accepted by all mathematicians because the computer-assisted 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;

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 2:52 am UTC

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

RabidAltruism
Posts: 135
Joined: Fri Aug 29, 2008 9:25 pm UTC

Re: Four color theorem

Postby RabidAltruism » Wed Mar 24, 2010 3:51 am UTC

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 computer-like in our algorithm-following 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 branch-and-bound or whatever optimization algorithm is, at algorithm's end, not proof-like 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...

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 » Wed Mar 24, 2010 5:25 am UTC

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 Apparatus-like in our algorithm-following abilities, I suspect it wouldn't take a proof involving hundreds of thousand of individual cases checked to reach a level of mon-keigh 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 branch-and-bound or whatever optimization algorithm is, at algorithm's end, not proof-like 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.

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 5:42 am UTC

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.

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

Re: Four color theorem

Postby DavCrav » Wed Mar 24, 2010 7:29 am UTC

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 computer-free 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 so-called quasithin simple groups. This was done at around 2000.

There was also the Robertson--Seymour 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.

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

Re: Four color theorem

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

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.

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 2:22 pm UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests