ec2-13-59-218-147.us-east-2.compute.amazonaws.com | ToothyWiki | RecentChanges | Login | Webcomic Given any map, what is the fewest number of colours you need to colour it, so any two countries which share a border don't have the same colour?
The answer (as proved by Appel and Haken, and not Whatshisname from ClareCollege at all) is four. ... as long as the map is in 2 dimensions.
...and can be drawn on the surface of a sphere (for a torus, the answer is 7, and this is allegedly much easier to prove sufficiency for).
Appel and Haken proved it by computer search. I was unaware either was ClareCollege.
Hang on. Whatshisname proved FermatsLastTheorem, not the four colour theory. I take it all back. --Angoel
Were you thinking of Dr. Andrew Wiles, the Fermat's Last Theorem chap?
Yeah - it's still not had a proper proof, instead they enumerated every possible set of corners and showed that a four colour solution existed. --Vitenka
Hehe. "Proper proof" is an interesting phrase to use. It's a valid mathematical proof, and is generally accepted for cases where you're enumerating 2 or 3 cases. When you're enumerating several thousand, somehow people stop viewing it as a "proper proof" in the same way. AlexChurchill can understand the feeling that it ought to be "properly provable", rather than just demonstrable for all cases... but still...
It's valid - but I can no more understand it than I could before someone let me play with maps for a while and said "Do you think this is true?" It's not an elegant proof, and I think it highlights a missing bit of maths - we need some nice way to enumerate and step through without actually having to do it. I suppose the really clever part was finding a way to enumerate and generate all possible maps (and show that they were all possible maps) - plus I can't help shake the nagging feeling that we'd have opened up a new field of art if they'd found a counterexample instead. "PenroseTiles, meet the five colour map." Something like that. Dang laws of nature, spoiling my fun and not even being able to show me why ;) --Vitenka
I guess we do have a way to 'enumerate and step through without actually having to do it' - that being induction, for those theories where it works. --Mjb67
And, indeed, the proof of the four colour theorem is inductive. It just happens to have a few thousand base cases.
Induction only works where the cases have an obvious progression and similar form - we need something where the progression is through the forms rather than through the cases of a form. Did that make sense? --Vitenka (But yeah, it's obviously be named something-induction)
It is. It starts with the few thousand base cases. Then shows that any map with N corners (or some such) can be split up into sub-cases of fewer-than-N corners, in such a way that if you could 4-colour the sub-cases, you can 4-colour the original map also. Induction.
Yes yes yes - I understand that. My point is that we need some way to step through non obviously related cases. Or to give another example, I can induct 1+1, 1+1+1, 1+1+1+1 - why can't I induct 1^1 1^1^1 1^1^1^1 where ^ ranges over +,*,**,? etc.
Are you confusing the theory with the method? Induction isn't a method of doing things, it's a theory that says, "If we do this (...), then it's been proved." The implementation of induction is up to the person coming up with the proof. If you find a way of proving, "If it's true for 1^1^...^1, then it's true for 1^1^...^1^1," then you can use the theory of induction to say it's been proved. The way that you step through cases is separate from the fact you're using induction.
I mean a method that lets you step through operators, rather than through cases, I guess. I suppose induction itself doesn't stop you - just that we don't have a rule to use it on. It's just that having a thousand base cases suggests to me that the proof is closer to a demonstration. I suppose it's because internally I equate numbers greater than 12 or so with infinity. So by showing it to be true for all eighteen hundred cases, they pretty much showed it as true for infinity to me - or at least as good as, since I can comprehend neither. --Vitenka
Well, no. But I know that ten exists, and thus can deduce that eleven should exist and be countable - and I don't reckon either of those should be greater than infinity. Hence, twelve. The real value is somewhere around three and a half, being the most dimensions I can envisage. --Vitenka
So what you're saying is that you agree it's induction - you just want the inductive step to be simpler, or based on induction itself? --Angoel
No no no no no - I agree that the induction is fine and works - once you've got the eighteen hundred base cases and possible steps sorted out. What I *want* is a way to find all of those cases and prove one from the other. There should be a deeper pattern, rather than just 'we can choose these colours and it works'. --Vitenka
PeterTaylor thinks that Vitenka is after a second partial ordering which allows an inductive proof of the base cases of the main induction from a handful of base cases. HTH.
That would do it. It'd make the proof messier and require multiple steps - but it would do it. Really I want something more general, about the connectedness (um, not the mathematical connectedness, I don't think. Something about how spiky they are and how many other shapes they can contact, and the spikiness of the resulting compound shape.) of shapes and the rules of the surface upon which they lay - which can then give a specific answer for a sphere. --Vitenka
![[Home]](/img/text_logo.jpg){kind=logo}
FourColourTheory