Hadwiger–Nelson problem
Encyclopedia
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 one from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 4, 5, 6 or 7. The correct value may actually depend on the choice of axioms for set theory
.
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 there is unit distance between the two points. Then 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 , 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.
According to , the problem was first formulated by E. Nelson in 1950, and first published by . 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 . discusses the problem and its history extensively.
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, named the Moser spindle
after its discovery by the brothers William and Leo Moser
, with chromatic number four. 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.
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 , this upper bound was first observed by John R. Isbell
.
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 (see, e.g.). Such restrictions may cause the required number of colors to increase, as they prevent certain colorings from being considered acceptable. For instance, if all color classes are required to be Lebesgue measurable, it is known that at least five colors are required. If all connected components of each color class are convex polygons with area bounded away from zero, then at least six colors are required .
Geometric graph theory
In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...
, the Hadwiger–Nelson problem, named after Hugo Hadwiger
Hugo Hadwiger
Hugo Hadwiger was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.-Biography:...
and Edward Nelson
Edward Nelson
Edward Nelson is a professor in the Mathematics Department at Princeton University. He is known for his work on mathematical physics and mathematical logic...
, asks for the minimum number of colors required to color the plane
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
such that no two points
Point (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...
at distance one from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 4, 5, 6 or 7. The correct value may actually depend on the choice of axioms for set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
.
The question can be phrased in graph theoretic terms as follows. Let G be the unit distance graph
Unit distance graph
In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one...
of the plane: an infinite graph with all points of the plane as vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
and with an edge between two vertices if and only if there is unit distance between the two points. Then 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 , 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.
According to , the problem was first formulated by E. Nelson in 1950, and first published by . 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 . discusses the problem and its history extensively.
Lower and upper bounds
Moser spindle
In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges...
after its discovery by the brothers William and Leo Moser
Leo Moser
Leo Moser was an Austrian-Canadian mathematician, best known for his polygon notation....
, with chromatic number four. 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.
The upper bound of seven on the chromatic number follows from the existence of a tessellation
Tessellation
A tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
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 , this upper bound was first observed by John R. Isbell
John R. Isbell
John Rolfe Isbell was an American mathematician, for many years a professor of mathematics at the University of Buffalo .-Biography:...
.
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 .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 (see, e.g.). Such restrictions may cause the required number of colors to increase, as they prevent certain colorings from being considered acceptable. For instance, if all color classes are required to be Lebesgue measurable, it is known that at least five colors are required. If all connected components of each color class are convex polygons with area bounded away from zero, then at least six colors are required .