Talk:Four color theorem: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>David J. Marcus
(→‎Four Colors Do Not Suffice: What is the "usual" defintion of "map"?)
imported>Peter Jackson
Line 67: Line 67:


::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. [[User:David J. Marcus|David J. Marcus]] 03:58, 29 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. [[User:David J. Marcus|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. [[User:Peter Jackson|Peter Jackson]] 09:07, 29 September 2010 (UTC)

Revision as of 04:07, 29 September 2010

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)