the four color theorem...
in [Math]
|
Prev: integral
Next: math category of probability Chapt 3, Telescope as the the finest Distance tool measure in astronomy; 400 million light years as 1 atom/m^3 #83; ATOM TOTALITY
From: riderofgiraffes on 13 May 2010 14:55 Your argument is that because you cannot have five mutually joined points, five colours cannot be necessary. That means that if I have a graph without four mutually joined points, four colours won't be necessary. Draw a pentagon, put a vertex in the middle (giving six vertices in total) and join that middle vertex to the five on the pentagon. You cannot find four vertices that are all mutually joined, so by your reasoning, it should not be necessary to require four colours. Three should suffice. And yet three do not suffice. The structure of the graph forces you to use four, even though you do not have four mutually joined vertices. In a similary fashion, perhaps there is a complex graph where the requirement for a fifth colour does not depend on local properties, but on global ones. A cycle can be two coloured if there are an even number of vertices, and yet not if there are an odd number of vertices.
From: Gerry Myerson on 13 May 2010 19:09 In article <50fb3093-2b90-4b73-ae25-fbbfc89fb96e(a)b18g2000yqb.googlegroups.com>, noemata <noemata(a)kunst.no> wrote: > First, I have to say that I'm not a mathematician. Maybe that's why I > don't understand why the four color theorem has been so difficult to > prove. > The theorem states that no more than four colors are necessary to > color > the regions of any map to separate them. > My understanding goes like this: > First you try to draw a counterexample. Then you realize it's > impossible. And then you realize why: All the regions have to touch > all > other regions There's your mistake. It is indeed easy to prove that you can't draw 5 regions so each touches all the others, but that doesn't even begin to prove the 4CT. You have to deal with the possibility that there's a map with lots of regions that needs 5 colors even though no 5 of its regions are mutually adjacent. Think about coloring the vertices of a pentagon. There is no set of 3 vertices, all adjacent to each other, but you still need 3 colors. -- Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: spudnik on 13 May 2010 23:17 to put it differently, Bucky thought that "behold, the tetrahedron" was a proof of 4CT, but it just shows the *neccesity* of (at least) four colors, not the sufficiency thereof. (and, of course, since the tetrahedron is self-dual, you can color the vertices, instead. which is to say, almost all treatments of 4CT use graphs, because it is exactly equivalent.) > Think about coloring the vertices of a pentagon. There is no set > of 3 vertices, all adjacent to each other, but you still need 3 colors. thus: so, a lightmill is that thing with black & white vanes on a spindle in a relative vacuum? you can't rely on "rocks o'light" to impart momentum to these vanes, only to be absorbed electromagnetically by atoms in them; then, perhaps, the "warm side" will have some aerodynamic/thermal effect on the air in the bulb, compared to the cool one. thus: even if neutrinos don't exist, Michelson and Morely didn't get no results! > Could neutrino availability affect decay rates? thus: every technique has problems. like, you can't grow hemp-for haemorrhoids under a photovoltaic, without a good lightbulb. the real problem is that, if Santa Monica is any indication, the solar-subsidy bandwagon is part of the cargo-cult from Southwest Asia (as is the compact flourescent lightbub, the LED lightbulb etc. ad vomitorium). > Government subsidies, and fat returns on PVs? --Light: A History! http://wlym.com
From: noemata on 14 May 2010 05:59 > There's your mistake. It is indeed easy to prove that you can't > draw 5 regions so each touches all the others, but that doesn't > even begin to prove the 4CT. You have to deal with the possibility > that there's a map with lots of regions that needs 5 colors even > though no 5 of its regions are mutually adjacent. Aha, now I see the problem. But it seems to be a problem of "proving" something that seems intuitively true in graph theory. That a proof has to deal with the possibility of a map that needs 5 colors seems to me to be something like: prove that there are no naturally green swans by checking all of them. And why should that constitute a proof since there's no guarantee for not finding a green swan in the future? Similarly, that another type of map, another formalism, should be discovered later? This type of proof also seems arbitrary, like: prove that no angels exist by dealing with the possibility that they exist. A proof would for instance go through all types of angels (archangel, seraphim, cherubim, etc) and on finding none of each conclude that no angel exists. Or go through types of human senses and conclude that if no angels are to be seen, heard, touched, etc. there's no need to believe they exist. In short, it doesn't seem satisfactory to me that a proof of 4CT has to deal with finding a possible map needing 5 colors. Because if this map doesn't exist, then 4CT cannot be proven (by not finding it) - 4CT can only be proven wrong by finding such a map. I guess it's a problem of falsifiability. It would be better with an analytical proof, and I'm still not sure why a proof via graph theory (as mentioned in the post) won't work, for instance by establishing a structural identity between 4CT and the graph. Thanks for your answer - Bjørn
From: riderofgiraffes on 14 May 2010 02:29
The 4CT claims that no planar map requires 5 colours. You seem to think that the only way to prove that is to check every planar map and see that it only requires 4 (at most). An equivalent would be this. I claim that no number of the form 4*k+3 can be written as the sum of two squares. By your reasoning the only way to know this for certain would be to check every number of the form 4*k+3 and see that it cannot indeed be written as the sum of two squares. What mathematics is about, though, is proof, reasoning by agreed techniques from agreed facts to show that other statements follow logically, and hence must be true. This has been done with the 4*k+3 statement, and it's been done with the 4CT. It has been shown *by reasoning* that no planar map requires 5 colours. The reasoning is long, moderately difficult, and complex, but it's now accepted as correct. It is, by the way, comparatively easy to show that no planar map requires 5 colours, and it's fairly trivial to show that no planar map requires 6 colours. If you are interested in this question, why don't you find explanations of those and study them as a warm-up. |