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: jbriggs444 on 14 May 2010 08:33 On May 14, 7:48 am, noemata <noem...(a)kunst.no> wrote: > 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. It's not a question of reducing the problem. It's a question of reducing your argument (which I have not read, so take this with a grain of salt). If your argument is not crucially sensitive to some qualitative distinction between four colors and five then it applies with equal force to the four color case. If it is invalid for the four color case (as it is, since there are counter-examples) then it is invalid for the five color case -- even if there are no counter-examples in that case.
From: David Rusin on 14 May 2010 16:56 In article <684908402.132611.1273791361907.JavaMail.root(a)gallium.mathforum.org>, riderofgiraffes <mathforum.org_am(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. Well, maybe you should say "In the spirit we might expect..." instead of "That means..." . It might be helpful to the OP to demonstrate a graph that really requires 5 colors but contains no K_5 . Building on the examples of other posts we might begin with a ring of 5 points (the vertices of a pentagon) and add two more vertices, each connected to all 5 of the original points as well as to each other. That way the pentagon requires 3 colors and each of the additional points requires an additional color. On the other hand any set of 5 mutually adjacent points would have to include at least 3 points of the pentagon, and no such set of 3 mutually adjacent points exists. This particular graph is not a counterexample to the 4CT because it is not planar, but the fact that it is not planar is not especially obvious, and moreover there is no obvious way to use the planarity of the graph to rule out a similar but more complex example that IS planar. dave
From: christian.bau on 14 May 2010 19:40 On May 14, 12:48 pm, noemata <noem...(a)kunst.no> wrote: > Now, probably it's better for me to study the answers and theorem more > rather than to think aloud - thanks again for useful help. It might be a good idea to google for "five colour theorem" or "five color theorem" - that's the theorem that every graph can be coloured using FIVE different colours. Obviously a much weaker theorem, but still not easy to prove. You'll find the proof on the internet - not more than page. The idea, and I hope you can follow the logic: Let's say not every map can be coloured with five colours. Let's say there are maps that need six colours to colour them, and no way to do it with five colours. Now if there are such maps, then there must be one with the smallest possible number of countries.(All maps up to a certain number of countries can be coloured in five colours, and with one more country you'll find maps that absolutely need six colours). So there must be a map that needs six colours, but if you remove any country, it can be coloured in five. Then there is a formula for the number of edges in a planar graph, and that formula shows that in a planar graph you can't have all countries having six or more neighbours, there must be some with five or fewer. So you take this graph that needs six colours. You remove a country with five or fewer neighbours. You colour the rest in five colours, and then you put the missing country back in. And then these guys prove that you could have coloured the whole map in five colours instead of six. The funny thing is that some time in the 19th century someone made a proof for the Four Colour Theorem using exactly the same idea, just a little bit more complicated - and it took eleven years until a tiny fault in the proof was discovered! So you should definitely have a look at the Five Colour Theorem.
From: ICA on 15 May 2010 02:22 On May 14, 1:54 pm, Chip Eastham <hardm...(a)gmail.com> wrote: > 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 Odd rings of size greater than three is the main source of the difficulty in the proof of the 4CT. In the revised version of my paper "A Victorian Age Proof of the Four Color Theorem" ( http://arxiv.org/abs/0903.4108 ) I have given an algorithm of breaking (or blocking) the big white odd rings (if there is any) in the maximal di-chromatic map M(B,G) where B denotes color brown for the high-land region and G denotes color green for the low-land region. Cahit
From: noemata on 16 May 2010 06:50
Reading and trying to reformulate of my argument: (1) A map that needs n colours contains a K_n as graph. (2) All maps can be restated as planar graphs. Then, a map that needs more than 4 colours is impossible because it would contain a non-planar K5 as graph. What about the counterexamples given, for example the pentagon graph needing 3 colours while only having 2 mutually joined vertices? I understand this as: while all maps can be restated as planar graphs, not all planar graphs can be restated as maps. When I try to draw the pentagon graph as map it reduces to a K3 as graph, which supports (1). There isn't a direct way to draw a map from a graph - the example with a pentagon with a vertex in the middle that requires 4 colours makes this clearer. But there might be a procedure for this purpose that reduces a planar graph to a K_n. For example, the node-list of the pentagon shows that a couple of nodes are redundant and so leaving us with a K3: 1: 2, 3 2: 1 (redundant, already in "2: 3, 1") 1: 2 (redundant, already in "1: 2, 3") 2: 3, 1 3: 1, 2 In this way, would a simplified proof of 4CT be possible? Since 4CT, as I understand it, is proven for all planar graphs, though not all planar graphs are maps, the proof is more complicated than necessary. Maybe all planar graphs /are/ maps, though not restate-able in a direct way. Maybe all graphs can be reduced to maps. My idea is that all planar graphs are reducible to a map as a K_n graph and thus requiring n colours. Grateful for comments, my main concern is the relation between maps and graphs. -Bjørn On May 14, 2:22 pm, riderofgiraffes <mathforum.org...(a)solipsys.co.uk> wrote: > > 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. |