5 ms·
I'm not a mathematician, but when I was in school I read a lot of 'pop math', and fancied myself a lot better at it than I was (or am). I was fascinated by thin
by OJFord 4y ago
I'm not a mathematician, but when I was in school I read a lot of 'pop math', and fancied myself a lot better at it than I was (or am). I was fascinated by things like the FCT, and recall writing a document ...I don't think I kidded myself proving it, but at least 'understanding' it.
The rough sketch was to show that it was not possible to construct a map that required five colours: that if you take a blob of one colour, wrap it in three others, all four are touching the others, but you can't possibly add a fifth since it either only touches the outer three, or it has to prevent two of them touching to get to the inner one (then the non-touching ones could be recoloured the same).
To this day, although I of course realise I was having no groundbreaking thoughts and it did not constitute a proof, I do not understand why the actual proofs are so complex, or require so much computation? It eluded far greater minds for over a century - what am I missing that makes it so problematic?
- bodhiandphysics 4y agoin some sense because there might be strongly non-local effects... an assignment of color in one part of the graph can have an effect on what colors are allowed in a very different part of the graph. Planarity assures some degree of "locality", you can't arbitrarily connect one point to another point.
- nicky0 4y agoYour proof sketch actually suggested that it was not possible to construct a map with five regions that require five colours. Now you need to generalise that to maps with infinitely many regions.
- OJFord 4y agoBut as a result there could never be an area of an infinitely large map that had five regions each needing a different colour. I understand people are saying but you take two such sub-maps, put them next to each other, and maybe the 'outside' colours are the same - but in that case you could always just recolour them individually before putting them together?
- ColinWright 4y agoWhat you've said here might be a reasonable reply in your head, but for me, reading its parent, and this reply, I can't work out what you're trying to say. You need to be really careful about things like "infinitely large map" ... if you want to talk about really large things then they are really large. But if you want to talk about infinite sized things then you need to be careful. There are traps in infinities, and this theorem is about finite maps (or equivalently, graphs). Proving that a small, local sub-section doesn't require five colours is helpful, but no one has been able to extend that, because there is a kind of "spooky action at a distance" that can happen. Local decisions about colours can lead to implications across the other side of the structure. Proving that your local decisions can always be made in a way that doesn't cause problems elsewhere is the problem. You are saying the sorts of things I've seen many times before, but you need to try to make complete, precise statements about exactly what you propose. So far all you've said is that you can't arrange five regions that all touch each other, and that's true. Now, exactly how do you extend that to a map with billions of regions?
- OJFord 4y agoIt was the comment I replied to that introduced infinitely large maps - but regardless I wasn't trying to be as clever as you might be trying to assume (and of course not finding it :)) - I would have said the same about 'really large' or indeed 'just a bit larger than the 4 or 5 regions I described initially'. > there is a kind of "spooky action at a distance" that can happen. Local decisions about colours can lead to implications across the other side of the structure. Proving that your local decisions can always be made in a way that doesn't cause problems elsewhere is the problem. This is the bit I can't grasp - I honestly appreciate the responses and attempts to explain it, but it just (mistakenly, I can accept even if I don't understand) seems counter-intuitive to me. As in, intuitive that it extends, or that there's no such problem. Maybe I just need to play with it on paper a bit, stumble into such a spooky action to get it. > Now, exactly how do you extend that to a map with billions of regions? I don't have the background for the precision you'd like I'm afraid (if I did, I'm sure I'd understand anyway!) but loosely - divide and conquer; a similar thing happens at the interface of all the 'sub-maps'?
- ColinWright 4y agoIt's (relatively) easy to prove that you can't have five regions that all touch each other. If you could then that would mean that a map requires (at least) five colours, but that's not the only way a map could require five colours. Even so, it's certainly the first thing to try. But colours-at-distance can be forced, so proximity isn't needed to create the need for another colour. The theorem is difficult for two meta-reasons. One is that there are arbitrarily many planar configurations, and you need to prove that they are all four-colourable. The other is that whether or not a planar graph is three colourable is NP-Complete, and showing a planar graph is five-colourable is fairly easy, so it's on the boundary between fairly easy and really hard. The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand. Appel and Haken's proof of the four-colour theorem proceeded the same way, but the unavoidable set was large. The computation was to confirm that the set was unavoidable, and that each element was reducable. This involved a huge amount of tedious bookkeeping, best done by machine, but it was really just "doing the sums". The real work was creating a finite amount of bookkeeping that would then constitute a proof.
- siftrics 4y agoThanks for the insightful comment. >The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand. Isn't this missing a crucial point? You seem to be saying: 1. There is some (small) set S of graphs, all of which are 5-colorable 2. Every planar graph has at least 1 sub-graph in S 3. Therefore, all planar graphs are 5-colorable But, from statements 1 and 2, one can only conclude that every planar graph _has a sub-graph_ that is 5-colorable, not that the entire graph is 5-colorable. Don't you also need to prove that the complement of the sub-graphs is 5-colorable?
- ColinWright 4y ago
- Someone 4y agoThat 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 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)
- OJFord 4y agoIf you don't have such a blob then you don't even need four?
- ColinWright 4y agoThis 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 https://en.wikipedia.org/wiki/Alexander_horned_sphere