Talk:Hadwiger–Nelson problem

Inception

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 (talk • contribs) 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

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

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

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

In n dimension, the most color is 2ⁿ, 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

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:

• Added archive https://web.archive.org/web/20110614010637/http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf to http://www.uccs.edu/~faculty/asoifer/docs/AXIOMOFCHOICEinJCT.pdf
• Added archive https://web.archive.org/web/20060830092649/http://maven.smith.edu/~orourke/TOPP/P57.html to http://maven.smith.edu/~orourke/TOPP/P57.html

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

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• 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.

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

Regions bounded by Jordan curves

In the section "Variations of the problem" the following sentence confused me: "For instance, if a coloring of the plane consists of regions bounded by Jordan curves, then at least six colors are required.". An article by Woodall and an article by Coulson are cited. Now truthfully, the article by Woodall I do not quite understand but both articles do not seem to have the restriction to be "regions bounded by Jordan curves". Woodall gives the restriction "if the sets are either closed or simultaneously divisible into region (in a sense to be made precise)" while Coulson has the restriction "6 colours are necessary for an excluded distance when convex polygonal tiles (all with areagreater than some positive constant) are used as the colouring base". I am not yet convinced that these conditions are the same as regions bounded by Jordan curves. Could someone help convince me or is there a mistake in the article? Thanks! EMHwiki (talk) 22:11, 27 February 2019 (UTC)