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: noemata on 14 May 2010 06:37 On May 14, 12:55 am, riderofgiraffes <mathforum.org...(a)solipsys.co.uk> wrote: > 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. I don't think it follows logically. You say: If x, then y. Conclusion: if not x, then not y. But that's not true, you can have y in another way. If it rains, then it gets wet. Conclusion: if it doesn't rain, it doesn't get wet. But it might still be wet, for other reasons. My argument I think goes like: Since it's impossible to mutually join 5 dots then it's impossible that 5 regions all have contact with each other. And because of that a map where 5 colors are necessary is impossible. As I understand it now the problem of the proof is that a map that needs 5 colors /is not necessarily/ a map where 5 regions have contact with each other. One imagines that such a map exists in some complicated way, but cannot find it. So I guess my question remains - why aren't we able to prove somehow that a map that needs 5 colors is structurally identical to a map where 5 regions have contact with each other? > > 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: Chip Eastham on 14 May 2010 06:54 On May 14, 5:59 am, noemata <noem...(a)kunst.no> wrote: > > 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 I think you missed riderofgiraffe's and Gerry's point, that four color theorem requires eliminating the possibility of maps that require five colors, not just the possibility of five mutually adjacent regions. They gave you an example to think about, a map in which no three regions are all adjacent to one another (in fact each region has only two neighbors that themselves do not touch), yet three colors are required for coloring. 1 / \ / \ 2 3 \ / 4-5 A "ring" of any odd number of regions (more than 3) will illustrate this phenomenon. A proof of 4CT has to "deal" with the possibility of a map requiring five colors just in the sense that it must in some way exclude this possibility (not, as you seem to say, by "finding" one). The known proofs do this in a rather concrete but tedious way (using computer checking) to show all planar maps have a four coloring (by reducing the number of cases to be checked to a large but finite number of possibilities, to which an algorithm may be applied). Although there are infinitely many different planar maps, the finite number of cases to check is established by analyzing "rings" of regions that divide the map into a section inside the ring and one outside the ring. You might be interested in these expositions: [Last doubts removed about the proof of the Four Color Theorem] (by Keith Devlin) http://www.maa.org/devlin/devlin_01_05.html [A computer-checked proof of the Four Colour Theorem] (by George Gonthier) http://research.microsoft.com/en-us/um/people/gonthier/4colproof.pdf The Wikipedia and Wolfram Mathworld articles are also worth a look. regards, chip
From: riderofgiraffes on 14 May 2010 03:04 >> 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. > > I don't think it follows logically. Let me say again. Your argument appears to be this: "It's impossible to have 5 mutually adjacent points, therefore it's impossible to require 5 colours." That's my understanding of your argument. That argument is not valid. If that argument were valid, this would also be valid. "If a map requires 5 colours then it must have five mutually adjacent points." If that argument were valid, then so would this: "If a map requires four colours then it must have four mutually adjacent points." But we know that last argument is invalid, because there are maps that require four colours, and yet which do not have four adjacent points. > You say: > If x, then y. Conclusion: if not x, then not y. No. that's not true, and it's not what I said. It's also mostly irrelevent for this discussion. > My argument I think goes like: > Since it's impossible to mutually join 5 dots then > it's impossible that 5 regions all have contact with > each other. OK, that's true. > And because of that a map where 5 colors are > necessary is impossible. Why? Is it simply because you can't imagine a situation where you have a map requiring 5 colours and yet which doesn't have 5 adjacent regions? Not good enough. > As I understand it now the problem of the proof is > that a map that needs 5 colors /is not necessarily/ > a map where 5 regions have contact with each other. Correct. > One imagines that such a map exists in some > complicated way, but cannot find it. So I guess > my question remains - why aren't we able to prove > somehow that a map that needs 5 colors is > structurally identical to a map where 5 regions > have contact with each other? To the best of my knowledge that's an interesting and useful conjecture, and it has been pursued. However, no proof using that approach has been produced. Here is what you seem to be saying: Conjecture: Any planar graph that requires 5 colours for a vertex colouring is (in some sense yet to be determined or defined) "structurally equivalent" to K_5 - the complete graph on 5 points. It's a valid method of attack, and it would be interesting to see how far you get with it.
From: noemata on 14 May 2010 07:48 On May 14, 1:04 pm, riderofgiraffes <mathforum.org...(a)solipsys.co.uk> wrote: > >> 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. > > > I don't think it follows logically. > > Let me say again. Your argument appears to be this: > > "It's impossible to have 5 mutually adjacent points, > therefore it's impossible to require 5 colours." > > That's my understanding of your argument. > > That argument is not valid. > > If that argument were valid, this would also be valid. > > "If a map requires 5 colours then it must have five > mutually adjacent points." > > If that argument were valid, then so would this: > > "If a map requires four colours then it must have > four mutually adjacent points." > > But we know that last argument is invalid, because > there are maps that require four colours, and yet > which do not have four adjacent points. > > > You say: > > If x, then y. Conclusion: if not x, then not y. > > No. that's not true, and it's not what I said. > It's also mostly irrelevent for this discussion. > > > My argument I think goes like: > > Since it's impossible to mutually join 5 dots then > > it's impossible that 5 regions all have contact with > > each other. > > OK, that's true. > > > And because of that a map where 5 colors are > > necessary is impossible. > > Why? Is it simply because you can't imagine a situation > where you have a map requiring 5 colours and yet which > doesn't have 5 adjacent regions? > > Not good enough. > > > As I understand it now the problem of the proof is > > that a map that needs 5 colors /is not necessarily/ > > a map where 5 regions have contact with each other. > > Correct. > > > One imagines that such a map exists in some > > complicated way, but cannot find it. So I guess > > my question remains - why aren't we able to prove > > somehow that a map that needs 5 colors is > > structurally identical to a map where 5 regions > > have contact with each other? > > To the best of my knowledge that's an interesting and > useful conjecture, and it has been pursued. However, > no proof using that approach has been produced. Here > is what you seem to be saying: > > Conjecture: Any planar graph that requires 5 colours > for a vertex colouring is (in some sense yet to be > determined or defined) "structurally equivalent" to > K_5 - the complete graph on 5 points. > > It's a valid method of attack, and it would be > interesting to see how far you get with it. Thanks for very useful comments, many of the comments here are, it's a great help. If any comments I made were inappropriate, please put it on my slow-wittedness. For instance I still don't agree on this one: > "If a map requires 5 colours then it must have five > mutually adjacent points." > > If that argument were valid, then so would this: > > "If a map requires four colours then it must have > four mutually adjacent points." I don't think the problem can be reduced like this. A complete graph of 5 points might be "qualitatively different" from one of 4 points in some respect. For instance, can adding points somehow be like adding dimensions - a 4D structure has different qualitites than a 5D structure? Or to take a silly example: If 5 workers can produce 5 cars, it doesn't mean that 4 workers can produce 4 cars. Maybe the production line requires 5 workers to produce at all. Again, sorry for the silly example, but I think it's valid. Now, probably it's better for me to study the answers and theorem more rather than to think aloud - thanks again for useful help. Bjørn
From: riderofgiraffes on 14 May 2010 04:22
> Thanks for very useful comments, many of the comments > here are, it's a great help. If any comments I made > were inappropriate, please put it on my slow-wittedness. Nothing was inappropriate, and some of these issues are obscure and difficult. > For instance I still don't agree on this one: > >> "If a map requires 5 colours then it must have >> five mutually adjacent points." >> >> If that argument were valid, then so would this: >> >> "If a map requires four colours then it must have >> four mutually adjacent points." > > I don't think the problem can be reduced like this. > A complete graph of 5 points might be "qualitatively > different" from one of 4 points in some respect. If it is qualitatively different then you need to include that in your statement. As it was, you seemed to be saying that requiring five colours must in and of itself imply that there are five mutually adjacent points. Maybe it does, maybe it doesn't, but it's not right to make that claim without then qualifying it. As stated, your method of reasoning seems to apply equally well to the four colour requires K_4 case, and we know that to be false. That then implies that the reasoning is faulty. If there is something special that starts to make it work in the five colour case then you need to make that clear. And as I said, you might be right. It might be the case that a planar graph requiring five colours does then imply the existence of a planar K_5. If you can prove that then you have a valid proof of the 4CT, the first one that doesn't require a computer. > Now, probably it's better for me to study the > answers and theorem more rather than to think > aloud - thanks again for useful help. Sometimes you need to mess around with things on your own first, before reading other people's proofs. Then you are in a better position to understand the subtlties and difficulties. Besides, sometimes you might find a proof that no one else has found. Unlikely, but possible. never stop experimenting. > Bjørn Rider. |