Talk:Four color theorem

From Citizendium
Revision as of 14:31, 2 October 2010 by imported>Peter Schmitt (→‎Four Colors Do Not Suffice: blame me --- but it served a purpose)
Jump to navigation Jump to search
This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
To learn how to update the categories for this article, see here. To update categories, edit the metadata template.
 Definition (A famous mathematical statement with a long history) For every planar graph, four colors suffice to color its vertices in such a way that adjacent vertices have different colors. [d] [e]
Checklist and Archives
 Workgroup category Mathematics [Editors asked to check categories]
 Talk Archive none  English language variant American English

Created.--Thomas Wright Sulcer 04:06, 19 April 2010 (UTC)

Needs more wikilinks by persons who know which mathematical articles we've got and what they're called. Could use more pictures of diagrams?--Thomas Wright Sulcer 04:18, 19 April 2010 (UTC)

Wow! Looks impressing. (I have only a slight idea of this matter.) Boris Tsirelson 06:11, 19 April 2010 (UTC)
You could also add an external link from WP to here (as I did for "plane" for instance); it does not add google juice, but can add readers. Boris Tsirelson 06:21, 19 April 2010 (UTC)
Thanks Boris!!! I no longer have a Wikipedia account but feel free to add the link from WP. The two equations are from WP and some of the proof-logic from WP is here, rewritten, but other than that I'd say it's 90% new.--Thomas Wright Sulcer 11:24, 19 April 2010 (UTC)
Could you forget that WP can be edited by everyone? Anyway, I did. By the way, I see, you did not use your sandbox for preparing it. I wonder, did you write all of it first on your computer, locally? Boris Tsirelson 12:21, 19 April 2010 (UTC)
Yes. My ninth grader mentioned it and I got curious. The Euler theorem checks out. Still, overall, I'm not satisfied that it does an adequate job of explaining things in the philosophical sense, but I think this CZ version here is the best one out there on the web (that I could find). It needs wikilinks but I'm less familiar with what other math articles CZ has. I'll be adding diagrams to get the idea across clearer.--Thomas Wright Sulcer 12:59, 19 April 2010 (UTC)

(undent) I'm also eager to see how this develops; the coloring problem was one of those mathematical things that computer science programs touched on but never really explored.

I'm wondering whether in twenty years some mathematician will come up with a better proof. Clearly the current one seems clumsy to me, like it should be logical, simple, clear. 633 possibilities -- clumsy.--Thomas Wright Sulcer 13:17, 19 April 2010 (UTC)

Mentioning your ninth grader reminds me of a book series I've always liked, but don't know is still being published: the New Mathematical Library. Emphasizing graphics rather than formal notation and derivations, it takes on topics such as group theory, topology, cryptography, etc., in a manner accessible to a bright high school student. Might be a very good background source.

Thanks for the refernce. I'll see if I can get that book for him and for me.--Thomas Wright Sulcer 13:17, 19 April 2010 (UTC)

Apropos not using sandboxes: I vary. Sometimes, whether I use a sandbox or not, I like to start writing in a word processor with outlining, more powerful editing, etc. Open Office may turn out better than Word 2003, although I may also start combining with string processing languages for large tables and such. I use the sandbox when I need to test wikitables and such, but otherwise, and admittedly with a lot of direct writing experience, start in mainspace. It would be nice if some subpages could be tested in userspace, but it is possible to do Related Articles without full R-template support. Howard C. Berkowitz 13:05, 19 April 2010 (UTC)

So that's your secret. It's been bugging me how prodigious a writer you are, and I'm impressed that when you work on things, they continually improve. Sometimes I feel there's a ceiling in which my writing can't get better, but you break through the ceilings all the time. I watch how your articles keep getting better and it challenges me to get up to your level.--Thomas Wright Sulcer 13:17, 19 April 2010 (UTC)

Colors on France

(CC) Photo: Peter Dutton
Time for lunch!

Think they're too loud. If others agree I can switch them. --Thomas Wright Sulcer 13:56, 19 April 2010 (UTC)

You may not use the colors of Freedom Fries or, for that matter, Poutine. Howard C. Berkowitz 14:12, 19 April 2010 (UTC)
One of the colours should be white because in the mathematical problem the outside is also a country. --Peter Schmitt 01:12, 20 April 2010 (UTC)

Rewrite

Tom, I agree that the article is good to read (and that it contains only minor mistakes), but it needs some major changes to make it into an encyclopedic article on this topic (instead of a report in a magazine). I hope you will not be disappointed when I shall soon begin to stepwise rewrite it. --Peter Schmitt 00:08, 20 April 2010 (UTC)

Peter, my sense is there are many articles in the mathematics are that are unwritten, substandard, bare bones, lacking information, without any pictures, which could use the talented expertise of someone with your qualifications and knowledge. My suggestion is focusing on articles needing attention first, like a nurse in triage, who knows, wisely, to attend to those cases which can be repaired and which are important. This article is, by comparison with most others in the mathematics area, relatively healthy, well-written, and clear, with good pictures and which is fun to read and, in my view, the best one out there on the web on this subject–far superior to Wikipedia's in terms of readability and information. To improve it, in my view, requires fleshing out the discharging procedure which I'll try to do this if I have time but other articles are concerning me at present, but adding a section on the discharging procedure would make it even stronger. I disagree with you that this article isn't encyclopedic and merely a report in a magazine -- I don't appreciate your assessment, but I respect that you're entitled to your opinion, and I encourage you, as well as everybody, to be more complimentary and appreciative of the hard work that people do (without pay) to build this encyclopedia. I found that the criticism Article X isn't encyclopedic, when I wrote at Wikipedia, was kind of a catch-all vague term which essentially meant "I don't like this". I worked hard on this article to get it ship-shape, and in my view it is a credible addition to Citizendium, and if you focus your efforts on what you consider to be fixing it by stepwise rewriting, then I, and perhaps others, may sense that your focus here isn't on improving Citizendium, but rather some personal agenda against my contributions here.--Thomas Wright Sulcer 12:20, 20 April 2010 (UTC)
Why accept or reject possible improvements a priori? It would be wiser to first present and discuss them here on the talk page, and then decide. Boris Tsirelson 07:29, 21 April 2010 (UTC)
I agree, Boris. If there are intelligent improvements, I'll approve that. What I was objecting to was the idea of extensive editing over time, not in and of itself. I've seen it used as code to totally rewrite an article; this happened to me on Wikipedia (and I let it happen since I was leaving there) and the so-called "improvements" were, in my view, for the worse. But given the reality that there are many mathematical topics where CZ has nothing, and should, as well as low caliber stubs that need revamping, I think it makes sense for us to focus on areas needing improvement. My sense is that the Four color theorem article, as it is now, is perhaps the best on the web, beating WP in terms of readability and charts (but I'm biased here), although, as I've suggested, fleshing out the last stages of the proof would definitely be an improvement; if I have time, I'll attempt it. Why fuss with it when there are many other areas needing improvement? Of course it's everybody's prerogative, but I'm trying to suggest how we can work so that the entire online encyclopedia benefits.--Thomas Wright Sulcer 11:10, 21 April 2010 (UTC)

What's needed

What's needed is fleshing out the last stages of the proof. Is there a good way to show this? I think that's the next step logically.--Thomas Wright Sulcer 00:26, 20 April 2010 (UTC)

Four Colors Do Not Suffice

See "Four Colors Do Not Suffice", Hud Hudson, The American Mathematical Monthly, Vol. 110, No. 5 (May, 2003), pp. 417-423, http://www.jstor.org/stable/3647828.

Hudson constructs a map requiring six colors. The regions in the map are all bounded and path connected and share a common boundary line segment. So, six colors are needed. Each region union the common boundary is not path connected. The construction is similar to the topologist's sine curve. Hudson also shows that for any n, there is a map that requires at least n colors.

Hudson thus disproves the following two statements:

  • Four colors are sufficient to color any map drawn in the plane or on a sphere so that no two regions with a common boundary line are colored with the same color.
  • Four colors are sufficient to color any dual graph (of a map drawn in the plane or on a sphere) so that no two vertices connected by an edge are colored with the same color.

Appel and Haken actually proved the following:

  • Four colors are sufficient to color any planar graph so that no two vertices connected by an edge are colored with the same color.

David J. Marcus 21:47, 17 September 2010 (UTC)

The example constructed in this paper is interesting, but it is not a counterexample to the Four-Colour Map Theorem because it is not a map in the usual sense. But, as I wrote earlier, the article still needs some work (not yet done). --Peter Schmitt 23:14, 17 September 2010 (UTC)
David, it is just great that you started contributing almost as soon as your were accepted as a member!! So many people register in Citizen who then never contribute, that it is a very nice surprise when a new member starts contributing very soon after registering. Keep it up!! Milton Beychok 02:37, 18 September 2010 (UTC)
Peter, what is the "usual sense" definition of "map" and where is this definition stated? Hudson notes that the two statements he disproves are given as theorems in Saaty and Kainen. I've got a copy of "Introduction to Graph Theory", second edition, by Douglas B. West. The only place West defines "map" (that I can find) is on page 5 saying, "Roughly speaking, a map is a partition of the plane into connected regions. Can we color the regions of every map using at most four colors so that neighboring regions have different colors?" A few sentences later, he states that the corresponding graph is planar, but doesn't offer a proof that I can see. Hudson's example disproves West's "rough" statement of the theorem. I think Hudson's map is a perfectly reasonable map. If such maps are to be excluded, some explicit hypotheses need to be added to the theorem to do so. Also, the hypotheses need to be used in the proof of the theorem. David J. Marcus 03:58, 29 September 2010 (UTC)
I'm inclined to agree that the article needs a proper definition. Here's my intuitive guess.
A boundary between two regions is a curve with either zero or two endpoints. Any point in a boundary that is not an endpoint must have a neighbourhood containing points from those two regions and no others. With a bit of luck this should get rid of the pathological cases.
While I'm here, I'd just like to add that France and Austria have not got a common boundary. Peter Jackson 09:07, 29 September 2010 (UTC)
Austria and France -- oops -- I never read the complete text ... I only browsed it.
And yes, there is no definition of "map" ... there are a lot more things to improve, I know.
The page was written by a non-mathematician, and for that it is done quite nicely. It shows what an average reader might want to find, and for an average user the notion of a map is not a problem. The heuristic idea works quite well.
A suitable definition of map would be as a tiling by topological disks. The transition to the dual graph is still not trivial (it involves the Jordan curve theorem) and is treated in detail by Fritsch-Fritsch.
A (thoroughly revised) version of this page could be turned into a non-technical introduction to the (map) problem and its history (moved to Four-Colour Map Theorem while the page Four-Colour Theorem treats the graph-theoretical problem (with more details).
--Peter Schmitt 10:42, 29 September 2010 (UTC)
I'm not sure of the precise definition of topological disc. Would it exclude the pathological case linked above? Peter Jackson 10:12, 30 September 2010 (UTC)
A topological disc is a set homeomorphic to a closed circular disc. In a tiling, the discs cover the plane (or the sphere) while their interiors form a packing (are pairwise disjoint. I have not had the opportunity to check the complete paper (only the first page at jstor) but the description of Zenopia shows that the closed countries will not cover the interior "border", (cf. this review). I do not think that these fine points need to be discussed in an (heuristic) introduction. But they should be mentioned and discussed later when the dual graph is explained. --Peter Schmitt 13:26, 30 September 2010 (UTC)
Ah yes, of course. Closed is the key point here, isn't it? Peter Jackson 16:19, 30 September 2010 (UTC)
I see people are fussing about the definition of the word "map" as well as insubstantial easy-to-correct details like which countries border which. What is needed is to add the discharging procedure. This proves the last stage of this theorem. How come it hasn't been done? If none of you supposed "mathematicians" can handle the discharging procedure, I suppose moi (you know me -- Mr "Average") will have to show you all how to do it.--Thomas Wright Sulcer 18:44, 1 October 2010 (UTC)
You mean that Peter pointed out three days ago that Austria doesn't border France and NO ONE changed it until PAUL WORMER returned to do so, even though other discussions went on during that time!? This does not speak well for the concept of "expertise" at CZ!!!! Hayford Peirce 16:55, 2 October 2010 (UTC)
Big deal: a geographical error in an unapproved mathematical article! What about a mathematical error in an approved mathematical article? Boris Tsirelson 18:35, 2 October 2010 (UTC)
It may not be a big deal to you, but to me a geographical error of such obvious magnitude is terrible, no matter *where* it occurs. Suppose that in an article about Chicken Kiev we had six different sentences each saying that Kiev is a major Austrian city next to the Korean border? You wouldn't feel affronted by such nonsense? And by the fact that after this mistake was pointed out no one at all bothered to correct it for three days -- even though competent editors/authors were clearly aware of the situation? Moreover, in this particular case, when you have such a blatant error, repeated time after time, how can you then trust anything *else* in the same article? Hayford Peirce 18:59, 2 October 2010 (UTC)

(unindent)
(While, mathematically, a geographical mistake is not important I agree that it should not stay. Thus:) I plead guilty, Hayford, that I did not correct it immediately when I read the comment, but wondered why (the other) Peter only mentioned it on the talk page, instead of correcting it. And later, again, why Tom did not correct it. (I would have returned later.) But, unexpectedly, it served a purpose: It showed that Paul is still observing and caring ... :-).

Tom: Writing a good (and correct) article on the discharging procedure is not as easy as you seem to think. Moreover, I would not include it in this page but on a page of it's own.

--Peter Schmitt 19:30, 2 October 2010 (UTC)