Hadwiger-Nelson problem

from Wikipedia, the free encyclopedia

The Hadwiger-Nelson problem is a problem in geometric graph theory named after Hugo Hadwiger and Edward Nelson . The minimum number of colors required is searched for in order to color a layer in such a way that two points with a distance of 1 have different colors. The problem could not be solved so far, so it belongs to one of the open problems of mathematics , but the solution can be restricted to the values ​​5, 6 or 7. The right solution probably depends on which axioms from set theory are assumed.

In terms of graph theory, the problem can be formulated as follows: Let G be a unit distance graph in the plane, i.e. an infinite graph in which the nodes are identical to the points in the plane. In addition, the points should be connected by an edge if and only if they have a Euclidean distance of 1. Then the Hadwiger-Nelson problem consists in determining the chromatic number of G. Consequently, the problem is often called “determining the chromatic number in the plane”. According to de Bruijn-Erdős' theorem , the problem (assuming the axiom of choice ) is equivalent to determining the largest chromatic number in a finite unit distance graph.

According to Jensen and Toft (1995), the problem was formulated as early as 1950 by Edward Nelson and published for the first time by Martin Gardner in 1960. Hadwiger showed in 1945 that every cover of the plane from five congruent closed sets contains an edge with distance 1 in one of their sets. Hadwiger also mentioned the problem in a later publication (1961). The problem and its history were discussed in detail by Soifer in 2008.

Upper and lower bounds

Seven-coloring of the plane and four-colorable unit distance graph, extreme examples for the upper and lower bound of the Hadwiger-Nelson problem.

The fact that the chromatic number of the level must be at least four follows from the existence of a four-color, but not three-color, unit distance graph with seven nodes, the so-called Moser spindle , named after the two brothers William Oscar Jules Moser and Leo Moser . This graph consists of two equilateral triangles connected at a common node x . On the opposite side of x there is another equilateral triangle with the nodes y and z, between which an edge also runs. The Moser spindle can also be generated graphically using the Hajós construction , which starts with two complete graphs with four nodes each ( ). If the plane could be three-colored, the coloring would cause the triangles to have y and z the same color as x . However, since y and z are connected by an edge, no valid coloring is possible. So at least four colors are required to color the graph and the associated level.

An improvement of this lower bound to 5 was only achieved in 2018, after more than 60 years, by the biologist Aubrey de Gray . In his paper he explicitly describes the construction of a unit distance graph which cannot be colored with four colors. To do this, he used a large number of Moser spindles linked together. The size of the graph given by de Gray is 1581 nodes. In the Polymath16 project , different scientists are trying to find a smaller unit distance graph that requires 5 colors. The currently smallest such graph has 510 nodes and was constructed by Jaan Parts in August 2019.

The upper bound of seven for the chromatic number follows from the existence of a subdivision of the plane into regular hexagons , the diameter of which must be slightly less than 1. Then seven colors can be arranged in a repeating pattern and you get a seven-color of the plane. According to Soifer (2008), this method was first discovered by John R. Isbell .

Problem variations

The problem can easily be extended to higher dimensions. In the third dimension, as in the plane, there is no clear solution. However, it has been shown that the chromatic number in this case must be between 6 and 15.

Colorings are also conceivable in which further conditions are attached to the point sets of each color class. Such restrictions could lead to an increase in the colors required, as certain colors would lose their validity. For example, if all connected components per color class are to be convex polygons , at least six colors are required.

See also

literature

  • Nicolaas Govert de Bruijn , Paul Erdős : A color problem for infinite graphs and a problem in the theory of relations . In: Nederl. Akad. Wetensch. Proc. Ser. A 54 . 1951, p. 371-373 .
  • KB Chilakamarri: The unit-distance graph problem: a brief survey and some new results . In: Bull Inst. Combin. Appl. 8 . 1993, p. 39-60 .
  • D. Coulson: A 15-coloring of 3-space omitting distance one . In: Discrete Math. 256 . 2002, p. 83-90 , doi : 10.1016 / S0012-365X (01) 00183-2 .
  • D. Coulson: On the chromatic number of plane tilings . In: J. Austral. Math. Soc. 77 (2) . 2004, p. 191-196 , doi : 10.1017 / S1446788700013574 ( online ).
  • Hallard T. Croft, Kenneth J. Falconer, Richard Kenneth Guy : Unsolved Problems in Geometry . Springer-Verlag, 1991 (Problem G10).
  • Martin Gardner : Mathematical Games . In: Scientific American 203/4 . 1960, p. 180 .
  • Hugo Hadwiger : Covering the Euclidean space by congruent sets . In: Portugal. Math. 4 . 1945, p. 238-242 .
  • Hugo Hadwiger : Unsolved Problems No. 40 . In: Elem. Math. 16 . 1961, p. 103-104 .
  • Tommy R. Jensen, Bjarne Toft: Graph Coloring Problems . Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995, pp. 150-152 .
  • Saharon Shelah , Alexander Soifer : Axiom of choice and chromatic number of the plane . In: Journal of Combinatorial Theory, Series A 103 (2) . 2003, p. 387-391 , doi : 10.1016 / S0097-3165 (03) 00102-X ( online [PDF]).
  • Alexander Soifer : The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators . Springer, New York 2008, ISBN 978-0-387-74640-1 .

Web links

Individual evidence

  1. ↑ Shelah and Soifer, 2003.
  2. ↑ A graph is - colorable ( ) if and only if every finite induced subgraph is - colorable .
  3. ^ Martin Aigner : Combinatorial Theory . Springer-Verlag , Berlin a. a. 1979, ISBN 3-540-90376-3 , pp. 410 .
  4. ^ De Bruijn and Erdős, 1951.
  5. ^ Aubrey DNJ de Gray: The Chromatic Number of the Plane Is at least 5 . In: Geombinatorics . tape 28 , 2018, p. 5-18 ( arXiv [PDF]).
  6. ↑ Polymath Project 16
  7. ^ Coulson, 2002; Radoičić and Tóth.
  8. ↑ Croft, Falconer and Guy, 1991.
  9. ^ Coulson, 2004.