Talk:Hadwiger–Nelson problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field:  Discrete mathematics

Colleagues, in the 1991 paper, and now "The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators" (Springer, NY, 2009), Alexander Soifer proved that this problem was created in Oct-Nov 1950 by Edward Nelson alone. Even Hadwiger admits that in his 1961 paper. Paul Erdos in his 1994 talk at FAU agreed with Soifer's attribution. It is certainly important to change everywhere, the title included, to The Edward Nelson problem.

Also, in the opinion of many, this is one of the premier problems of mathematics, not medium level as indicated here. I suggest to correct. —Preceding unsigned comment added by Letranger1 (talkcontribs) 02:29, 8 May 2009 (UTC)

What is the meaning of "well-behaved region boundaries" here? --219.78.172.122 01:06, 25 November 2006 (UTC)

I changed this to a more specific and better referenced claim. —David Eppstein 22:11, 26 November 2006 (UTC)

How many colors are necessary and sufficient to color a 3D space? 213.220.248.216 07:45, 17 January 2007 (UTC)

See first paragraph of the "variations" section. I just added a reference for the claim there, but didn't otherwise change the text that already answers what is known for your question. —David Eppstein 08:01, 17 January 2007 (UTC)

Axiom of choice[edit]

Is the "choice of axioms" mentioned in the introduction just the assumption/rejection of the Axiom of choice? Does this mean that the "result of de Bruijn & Erdős (1951)" uses this axiom? --80.129.79.43 (talk) 21:21, 1 July 2008 (UTC)

  1. de Bruijn and Erdős do use choice. They show that ZFC implies that the chromatic number of the whole plane = max chromatic number of a finite subgraph.
  2. Let F4 be the statement that the maximum chromatic number of a finite subgraph of the plane is 4. The truth or falsity of F4 doesn't depend on choice, I think, but it is consistent with current knowledge that it's true.
  3. ZFC ∩ F4 ⇒ (χ = 4) by de Bruijn and Erdős.
  4. Falconer showed that at least five colors are needed to color the plane in such a way that every color class is Lebesgue measurable.
  5. Soifer and Shelah consider the axiom system ZF+DC+LM, where DC is dependent choice and LM is the axiom that all sets of reals are Lebesgue measurable. They observe that Solovay showed ZF+DC+LM to be equiconsistent with ZFC. But, by Falconer, ZF+DC+LM ⇒ (χ ≥ 5).
  6. Therefore, F4 ⇒ (ZFC and ZF+DC+LM lead to different chromatic numbers for the plane).
  7. Soifer and Shelah also provide a more extreme example, of a graph in which the vertices are the points of the real line and two vertices are connected by an edge if their distance is q+√2 where q is rational. They show that this graph has chromatic number 2 under ZFC, but uncountable chromatic number under ZF+DC+LM.
  8. I don't know whether it's possible for there to be three or four equiconsistent axiom systems each leading to a different answer to the Hadwiger–Nelson problem.
David Eppstein (talk) 21:46, 1 July 2008 (UTC)

Hexagonal tesselation[edit]

I don't see how the hexagonal tesselation works. If I repeat the given pattern across the plane in the obvious way I see many same-colored points at distance 1. There would be dark blue hexagon right at the top, one edge length away from the leftmost existing dark blue hexagon. Most likely I'm just missing something, I usually am when I comment on a math page. But at any rate it's not clear to me how it works. --Psellus (talk) 19:52, 12 May 2011 (UTC)

The edge length is not 1, it is slightly less than 1/2, so that the diameter of the hexagons (the distance between the farthest two points within a single hexagon) is slightly less than one. With this choice of edge length the closest pair of points in different hexagons with the same color is greater than 1. Maybe it is not sufficiently clear what to do to repeat the pattern? If a hexagon H is on the boundary of the drawing, the color of the neighboring hexagons can be determined by finding another hexagon with the same color as H and using the same pattern. For instance, the color of the hexagon directly above the red hexagon on the top left corner of the diagram is pink, the same as the color of the hexagons directly above the other three red hexagons. So the hexagons of a single color are spaced apart from each other on a big equilateral-triangle grid; you can see two equilateral triangles with red hexagons at their corners and the pattern continues the same way. —David Eppstein (talk) 20:10, 12 May 2011 (UTC)

External Link[edit]

I added a link to a tool I built for constructing graphs with edges of unit length. If this is inappropriate feel free to remove.

I don't think the link is particularly helpful for this problem. (1) any example that requires more than four colors is likely to be huge; (2) your applet doesn't have features for determining the chromatic number of a graph (instead it appears coloring must be done manually, and the default is uncolored); (3) most importantly, your applet doesn't prevent vertices from being placed on top of each other, making it very difficult to build any nontrivial graphs. It also seems problematic with respect to WP:ELNO #11. —David Eppstein (talk) 06:57, 8 August 2012 (UTC)

n dimension[edit]

In n dimension, the most color is 2n, right? — Preceding unsigned comment added by 101.10.10.197 (talk) 16:43, 26 July 2014 (UTC)

Read the article. Even in three dimensions the exact value is not known: "As with the version on the plane, the answer is not known, but has been shown to be at least 6 and at most 15." —David Eppstein (talk) 18:22, 26 July 2014 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified 2 external links on Hadwiger–Nelson problem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—InternetArchiveBot (Report bug) 20:29, 27 October 2017 (UTC)