Hadwiger–Nelson problem

In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 5, 6 or 7. The correct value may depend on the choice of axioms for set theory.[1]

Unsolved problem in mathematics:
How many colors are needed to color the plane so that no two points at unit distance are the same color?
(more unsolved problems in mathematics)
A seven-coloring of the plane, and a four-chromatic unit distance graph in the plane (the Moser spindle), proving that the chromatic number of a plane is bounded above by 7 and below by 4.
The Golomb graph, Solomon W. Golomb's ten-vertex four-chromatic unit distance graph

Relation to finite graphs

The question can be phrased in graph theoretic terms as follows. Let G be the unit distance graph of the plane: an infinite graph with all points of the plane as vertices and with an edge between two vertices if and only if the distance between the two points is 1. The Hadwiger–Nelson problem is to find the chromatic number of G. As a consequence, the problem is often called "finding the chromatic number of the plane". By the de Bruijn–Erdős theorem, a result of de Bruijn & Erdős (1951), the problem is equivalent (under the assumption of the axiom of choice) to that of finding the largest possible chromatic number of a finite unit distance graph.

History

According to Jensen & Toft (1995), the problem was first formulated by Nelson in 1950, and first published by Gardner (1960). Hadwiger (1945) had earlier published a related result, showing that any cover of the plane by five congruent closed sets contains a unit distance in one of the sets, and he also mentioned the problem in a later paper (Hadwiger 1961). Soifer (2008) discusses the problem and its history extensively.

Lower and upper bounds

The fact that the chromatic number of the plane must be at least four follows from the existence of a seven-vertex unit distance graph with chromatic number four, named the Moser spindle after its discovery in 1961 by the brothers William and Leo Moser. This graph consists of two unit equilateral triangles joined at a common vertex, x. Each of these triangles is joined along another edge to another equilateral triangle; the vertices y and z of these joined triangles are at unit distance from each other. If the plane could be three-colored, the coloring within the triangles would force y and z to both have the same color as x, but then, since y and z are at unit distance from each other, we would not have a proper coloring of the unit distance graph of the plane. Therefore, at least four colors are needed to color this graph and the plane containing it. An alternative lower bound in the form of a ten-vertex four-chromatic unit distance graph, the Golomb graph, was discovered at around the same time by Solomon W. Golomb.[2]

In 2018, computer scientist and biologist Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph. The proof is computer assisted.[3] Mathematician Gil Kalai[4] and computer scientist Scott Aaronson[5] posted discussion of de Grey's finding, with Aaronson reporting independent verifications of de Grey's result using SAT solvers. Kalai linked additional posts by Jordan Ellenberg and Noam Elkies, with Elkies and (separately) de Grey proposing a Polymath project to find non-4-colorable unit distance graphs with fewer vertices than the one in de Grey's construction. As of 2018, the smallest known graph with chromatic number 5 had 553 vertices Heule (2018), but in August 2019 Jaan Parts found a 510-vertex example.[6] The page of the Polymath project, Polymath (2018), contains further research, media citations and verification data.

The upper bound of seven on the chromatic number follows from the existence of a tessellation of the plane by regular hexagons, with diameter slightly less than one, that can be assigned seven colors in a repeating pattern to form a 7-coloring of the plane. According to Soifer (2008), this upper bound was first observed by John R. Isbell.

Variations of the problem

The problem can easily be extended to higher dimensions. In particular, finding the chromatic number of space usually refers to the 3-dimensional version. 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.[7]

In the n-dimensional case of the problem, an easy upper bound on the number of required colorings found from tiling n-dimensional cubes is . A lower bound from simplexes is . For , a lower bound of is available using a generalization of the Moser spindle: a pair of the objects (each 2 simplexes glued together on a facet) which are joined on 1 side by a point and the other side by a line.

One can also consider colorings of the plane in which the sets of points of each color are restricted to sets of some particular type.[8] Such restrictions may cause the required number of colors to increase, as they prevent certain colorings from being considered acceptable. For instance, if a coloring of the plane consists of regions bounded by Jordan curves, then at least six colors are required.[9]

See also

Notes
  1. Soifer (2008), pp. 557–563; Shelah & Soifer (2003).
  2. Soifer (2008), p. 19.
  3. de Grey (2018).
  4. Kalai (2018)
  5. Aaronson (2018)
  6. Comment by Parts on Polymath Thread 16, August 3, 2019
  7. Coulson (2002); Radoičić & Tóth (2003).
  8. See, e.g., Croft, Falconer & Guy (1991).
  9. Woodall (1973); see also Coulson (2004) for a different proof of a similar result.

References
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.