Hadwiger–Nelson problem

The Hadwiger -Nelson problem is named after Hugo Hadwiger and Edward Nelson problem of geometric graph theory. Is searched for the minimum required number of colors, for coloring a plane such that any two points with a distance of 1 are of different colors. The problem has not yet been clearly resolved, that belongs to one of the open problems of mathematics, however, the solution can be to the values ​​4, 5, 6 or 7 limit. The correct answer probably depends on what axioms are assumed from the set theory.

The problem can be formulated as graph theoretical follows: Let G be a unit distance graph in the plane, ie 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 there is the Hadwiger -Nelson problem in the determination of the chromatic number of G. Thus, it is often also called "Determination of the chromatic number in the plane " the problem. By the theorem of Erdös and de Bruijn, the problem is (assuming the axiom of choice ) is equivalent to determining the largest chromatic number in a finite unit distance graph.

According to Jenson and Toft (1995 ) according to which the problem has been formulated in 1950 by Nelson and 1960, published by Gardner for the first time. Hadwiger in 1945 showed that every cover of the level of five congruent closed sets contains an edge with distance 1 in one of their sets. Hadwiger mentioned the problem in a later publication ( 1961). The problem and its history have been extensively discussed in 2008 by Soifer.

Upper and lower bounds

The fact that the chromatic number of the plane must be at least four, it follows from the existence of a vierfärbbaren but not dreifärbbaren unit distance graph with seven nodes, the so-called Moser spindle, named after the two brothers, William and Leo Moser. This graph is composed of two equilateral triangles which are joined at a common node x. Is in each case a further equilateral triangle with nodes y and z, which also extends between an edge on the opposite side of x. The Moser spindle can also be generated using the graph-theoretical Hajos - construction in which one starts with two complete graph with four nodes (). If the plane were three-colorable, the coloring would cause the triangles that y and z get the same color as x. Since Y and Z are, however, connected by an edge, a valid color is possible. Thus, ie at least four colors are needed to color to the graph and the corresponding level.

The upper bound of seven for the chromatic number follows from the existence of a partition of the plane into regular hexagons, whose diameter must be less than 1. Then let seven colors in a repeating pattern arrange and obtained a seven - coloring of the plane. After Soifer (2008), this method was first discovered by John R. Isbell.

Problem variations

The problem can be easily extended to higher dimensions. In the third dimension there are like in the plane no unique solution. However, it was shown that the chromatic number must be in this case 6-15.

Are also conceivable dyes, where one builds further terms on the sets of points of each color class. Such restrictions could lead to an increase in the required colors, as certain dyes would lose their validity. If, additionally, all color classes be Lebesgue measurable, for example, at least five colors are needed. Make all connected components per color class convex polygons represent at least six colors are necessary.