News for hackers. Stuff that matters.
[dead]
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by umanwizard on Wednesday April 18, 2018 @08:13AM (#16866680)
I don't think a comment on HN has ever made me as viscerally upset as this one.

It's just the epitome of hubris. People have been trying to find counterexamples since at least the 19th century, without success, and now that a formal proof has come around, none of the thousands of professional research mathematicians alive has found any flaw with it.

But no, they must all be wrong, because of your (trivial and very easy to come up with) counterexample! Nope, the counterexample was shown wrong in minutes.

The worst part isn't that you didn't see how your example could be 4-colored. That's fine, everyone makes mistakes in mathematics. The worst part is that you have such a low opinion of everyone else's intellectual abilities that instead of asking "am I understanding the problem statement wrong?" or "what's the four-coloring of this graph that I'm missing?" you simply assert that you're right and the entire field of specialist mathematicians is wrong. Do you really think your counterexample is so shockingly clever that you're the only person capable of coming up with it in 150 years?

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by fulmicoton on Wednesday April 18, 2018 @07:44PM (#16872247)
Your comment made me feel a little better.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by whorleater on Wednesday April 18, 2018 @09:04AM (#16867016)
I'm endlessly amused by him confusing the words "theory" and "theorm"
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by jcranmer on Wednesday April 18, 2018 @12:38AM (#16864664)
You're horribly mistaken, but rather than just say that you're an idiot because there's a proof that every planar graph is 4-colorable, let me explain your confusion.

You are trying to construct a complete graph on N vertices in the plane, giving an example for N=5. This cannot be done. Indeed, every graph is either planar xor contains either the complete graph on 5 vertices or the bipartite graph of 3 vertices in each group as an implied subgraph.

You can embed a complete graph on N vertices in 3 dimensions easily, with thin rods. But this doesn't work for 2 dimensions because that connecting line divides 2-d space, so you can't cross it with another line. This property imposes some sharp constraints on what planar graphs have to look like, with implications for its colorability. The Four-Color theorem amounts to an exhaustive enumeration of the possible situations arising from these constraints and then showing that all of them can be colored with only 4 colors.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by lisper on Tuesday April 17, 2018 @05:49PM (#16862616)
Here's a chance for you to make some easy money: I'l bet you any amount you care to wager that I can color any planar map you can produce an actual drawing of with four colors.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by Someone on Wednesday April 18, 2018 @02:28AM (#16865136)
Be careful in how you phrase that. I would say graph where you say map.

Using map opens you to claims such as that a map containing the North Sea, the kingdom of the Netherlands, the kingdom of Belgium, the French Republic and the Federal Republic of Germany can’t be four-colored because they all border each other (the kingdom of the Netherlands and the French Republic on Saint Martin in the Caribbean)

Historically, other examples likely existed, as land ownership tended to be patchy in feudal Europe, and, later, colonies added borders between various European countries.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by hinkley on Tuesday April 17, 2018 @08:46PM (#16863717)
For convex shapes, isn’t it?
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by lisper on Tuesday April 17, 2018 @09:27PM (#16863914)
Huh??? Are you asking whether the 4-color theorem only applies to maps with only convex shapes? If so, the answer is no, the theorem applies to any planar map.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by fulmicoton on Wednesday April 18, 2018 @07:45PM (#16872253)
I think he meant connex.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by pc86 on Friday April 20, 2018 @09:44AM (#16884680)
Connex isn't a word, so that's unlikely. Convex is, but that's also not what he meant.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by hermitdev on Tuesday April 17, 2018 @06:08PM (#16862739)
https://imgur.com/iU7oc8d

Theories are not laws; only takes one counter-example to disprove them.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by jnky on Tuesday April 17, 2018 @06:11PM (#16862763)
Is this a joke? The four color theorem is a proven theorem and not some crackpot theory.

https://i.imgur.com/m3Ruasq.png

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by bronson on Tuesday April 17, 2018 @06:15PM (#16862779)
You didn't even try it, did you? Took 10 seconds.

https://imgur.com/a/1sdJ6

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by profosaur on Wednesday April 18, 2018 @06:13AM (#16866098)
I love that OP was at least willing to provide an example of a planar map that he believed could not be 4-colored. Credit for sticking his neck out.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by yoda222 on Friday April 20, 2018 @04:49AM (#16883209)
Red, blue, yellow, green. And white. That's five colors! ;-)
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by qntty on Tuesday April 17, 2018 @06:47PM (#16862967)
This is like a textbook case of the Dunning-Kruger effect
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by selestify on Wednesday April 18, 2018 @03:30AM (#16865429)
I'm really glad I'm almost never this cocksure of myself. I can't imagine the embarrassment.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by taneq on Tuesday April 17, 2018 @10:27PM (#16864143)
There's a difference between a "theory" (in popular usage) and a "theorem" (in a field like mathematics).

A theory is a hypothesis. It's a plausible-but-unproven guess.

A theorem is a fact which is known because it has been proven.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by umanwizard on Wednesday April 18, 2018 @10:33AM (#16867683)
Just to be clear: "theory" has a lot of different meanings, depending on the context. It can mean "hypothesis", but I can think of at least three other meanings, with example phrases: "Marxist theory"[1], "the theory of evolution"[2], "group theory"[3]...

As you're probably aware, this confusing patchwork of similar and overlapping yet distinct meanings is ripe for abuse: it's what allows people to get away with saying things like "evolution is just a theory".

[1] Here it means "the collective body of work of some school of thought".

[2] "A widely-accepted, well-tested scientific explanation for a phenomenon".

[3] "A subfield of mathematics; the set of definitions, theorems, and techniques related to a particular type of abstract object" (in this case, groups).

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by taneq on Wednesday April 18, 2018 @09:20PM (#16872645)
Yeah, the word "theory" is heavily overloaded and I wanted to keep it snappy so I just specified "general usage" and "in mathematics" to try and keep it on track. :)
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by selestify on Wednesday April 18, 2018 @03:29AM (#16865416)
I would correct that, for physics at least -- "theory" is just an explanation for something. "Law" is an experimental observation that holds true, but doesn't provide an explanation. E.g. Newton's laws describe macroscopic non-relativistic motion pretty well, but do not explain motion. The theory of relativity, on the other hand, explains the description of a bunch of physical phenomena, and also has lots of evidence behind it.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by lvoudour on Wednesday April 18, 2018 @05:46PM (#16871507)
Theories are not laws; only takes one counter-example to disprove them

I agree, apparently it only took a couple of minutes in mspaint to disprove yours :)

On a serious note, what hermitdev did we've probably all done at some point in our past, especially in our youth (disparaging long-standing theories about life, science, philosophy, etc.), no need to be mean.

Few times this leads to groundbreaking revelations that help humanity progress, but most times it leads to the embarrassing conclusion that past generations were not idiots.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by dreamcompiler on Thursday April 19, 2018 @02:32AM (#16873780)
When I was in high school I was convinced I could trisect an angle using compass and straightedge, and I told my math teacher so. He just smiled and said "Prove it."

He was a good guy. Took me several days to finally understand my mistake, but afterward I had a much better understanding of the problem

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by lisper on Tuesday April 17, 2018 @06:11PM (#16862759)
So put your money where your mouth is. How much are you willing to wager?
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by slx26 on Wednesday April 18, 2018 @03:58AM (#16865568)
there are more than 7 billion people in the world. every 4.2 seconds, we collectively live more than 100 years. there's a lot of clever-thinking time in a day, it's always nice to keep that in mind
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by ErikCorry on Wednesday April 18, 2018 @03:50PM (#16870505)
I guess that's technically true, since 931 years is more than 100 years.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by slx26 on Thursday April 19, 2018 @02:18PM (#16878519)
yeah, sorry, that was a typo, it's 1000, not 100. I calculated it a while ago. now population estimations are around 7.61 billions, which is around 1014 years every 4.2 seconds. it's an impressive amount of time
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by est on Wednesday April 18, 2018 @01:41AM (#16864934)
upboated for providing a pic. Thanks man but sorry man.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by mortehu on Tuesday April 17, 2018 @05:59PM (#16862694)
I can't understand your description, but if you can connect any number of nodes to all other nodes in a single plane, you may have a career in electronic circuit design.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by bronson on Tuesday April 17, 2018 @06:02PM (#16862709)
> It's a rather easy formula

So what are you waiting for? Draw it up. You'd shake the very foundations of mathematics.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by meeton on Tuesday April 17, 2018 @05:49PM (#16862615)
... I guarantee that if you draw that out for us, someone will 4-colour it for you. That's what "theorem" means.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by Sniffnoy on Tuesday April 17, 2018 @05:57PM (#16862679)
Your construction is a bit hard to understand. Would you mind describing it as an explicit plane graph, rather than in terms of a "map"?
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by IshKebab on Tuesday April 17, 2018 @05:48PM (#16862612)
"This mathematical theory that has been proven is bunk"

Right... Either you're misunderstanding what the theory says or your crazy concentric countries idea doesn't work (hard to tell from your description).

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by hermitdev on Tuesday April 17, 2018 @06:06PM (#16862731)
Like I said, describing it is hard, but showing it is not See this: https://imgur.com/iU7oc8d There's no way to color that with 4 colors without a color hitting itself. Yes, it's contrived, but so are borders. Also, the 4-color theorem didn't limit itself to established borders, it claims to be for an arbitrary map. This image, is well, arbitrary and drawn up in paint in a few minutes, but it shows the point.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by Sniffnoy on Tuesday April 17, 2018 @06:12PM (#16862770)
You're mistaken about that not being 4-colorable. Color the "rings", from outside to inside: red, blue, green, blue, yellow.

Again, as mentioned in my earlier comment, I would suggest thinking of things / describing things in terms of plane graphs rather than "maps". It'll make everything easier.

I might also suggest learning some of the relevant graph theory? It sounds like you're trying and failing to embed a K_5, or perhaps an arbitrary K_n, into the plane. That can't be done, and the proof that this is impossible is much easier than the full 4-color theorem. (There are also the 5-color and 6-color theorems, which again have much easier proofs than the 4-color theorem, and which are another reason you can't embed an arbitrary K_n in the plane.)

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by guskel on Tuesday April 17, 2018 @06:12PM (#16862766)
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by kr99x on Tuesday April 17, 2018 @06:11PM (#16862755)
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by benchaney on Tuesday April 17, 2018 @06:12PM (#16862767)
You can do R G B Y B from the inside working out.

The third and fifth rings (counting from the inside) don’t touch each other so, you can give them the same color.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by ClassyJacket on Tuesday April 17, 2018 @06:09PM (#16862751)
"It's a rather easy formula to produce a "map" that requires N colors if no two colors are to touch."

Then please do, we'd all love to see it.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by adrianratnapala on Wednesday April 18, 2018 @07:32PM (#16872186)
Although you can start with a bulls-eye of concentric ring-countries; once you start making enough of these isthmuses into the centre, then some of those countries must be broken up into "arc-islands".

You are correct that O(N) colours are needed if all the islands of one ring-country must have the same colour. But to encode that constraint graph-theoretically you would need "bridges" (edges) over isthmuses, which would make the thing non-planar.

Re:Decades-Old Graph Problem Yields to Amateur Mathematician by samkone on Wednesday April 18, 2018 @05:26PM (#16871355)
Dude, my whiskey is almost over, still waiting for you to shatter centuries of mathematical foundations. Don't make me wait too long please. Getting drunf af.
Re:Decades-Old Graph Problem Yields to Amateur Mathematician by cecilpl2 on Tuesday April 17, 2018 @05:56PM (#16862676)
You know you have a giant prize and glory awaiting you right?