Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That shows (loosely) that there is no map with five countries that cannot be four-colored. It says nothing about maps with six, seven, etc. countries. An actual map may have billions of countries and need not even contain “a blob of one colour, wrapped in three others”.

Loosely because

a) it only shows it for such maps that contain such a blob. Who says other maps with five countries are easier to four-color?

b) it doesn’t rigorously show it. That you (and me, and everybody who looked at it) can’t find a way to draw that fifth area that touches all others doesn’t say much. what are your arguments for showing you looked hard enough?

For a similar case, read about the Jordan curve theorem. In layman’s terms, it says closed curves on a plane have an inside and an outside part (https://en.wikipedia.org/wiki/Jordan_curve_theorem). Naive readers think it’s so trivial to not require a proof, and it took mathematicians a while to figure out that it needed one. I don’t know the details, but mathematicians may have observed that that theorem also is true on a sphere but isn’t true on a torus (a closed loop ‘around the hole’ in the torus doesn’t have an interior and an exterior). So, they needed an explanation as to why it’s true on a plane or a sphere but not on a torus (the answer essentially boils down to “because a torus has a hole in it”, but that requires a rigorous definition of what a hole is)



If you don't have such a blob then you don't even need four?


This is in the grandparent comment:

"An actual map may have billions of countries and need not even contain “a blob of one colour, wrapped in three others”."

In fact every map of interest will contain a blob wrapped in at least three others.

But they are right that the problem is showing that the theorem holds for maps with billions of regions, or more. Decisions you make early in the process of colouring the map can turn out to be wrong, but only much later as you are trying to colour the last few.

In short, you are saying "I can't see how it can go wrong", but that's not enough ... there are things that might happen that you weren't able to imagine, and that's part of why proofs like this are hard.

Also, the theorem is true, and that makes it hard to explain why it might go wrong. Because we now know that it doesn't.

The grand-parent comment also says:

"... the Jordan curve theorem ... is true on a sphere ..."

The stronger form is not true on a sphere. The stronger form says that every topological sphere in 3-space has an interior that's retractable to a point and an exterior that's retractable to a shell. But the Alexander Horned Sphere[0] is a counter example.

In short, weird things you didn't suspect can happen, so proofs are sometimes harder than you think, even for "obvious" things.

0: https://en.wikipedia.org/wiki/Alexander_horned_sphere




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: