Hadwiger–Nelson problem

Hadwiger–Nelson problem
Unsolved problems in mathematics
How many colors are needed to color the plane so that no two points at unit distance are the same color?

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 (Shelah & Soifer 2003).

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

According to Jensen & Toft (1995), the problem was first formulated by E. Nelson in 1950, and first published by Gardner (1960). Hadwiger (1945) 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.

Contents

Lower and upper bounds

A seven-coloring of the plane, and a four-chromatic unit distance graph in the plane, providing upper and lower bounds for the Hadwiger–Nelson problem.

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. The Moser spindle may also be constructed graph-theoretically using the Hajós construction starting with two complete graphs on four vertices. 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 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 (Coulson 2002; Radoičić and Tóth).

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., Croft, Falconer & Guy 1991). 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 (Coulson 2004).

See also

References

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Hadwiger–Nelson-Problem — Das Hadwiger–Nelson Problem ist ein nach Hugo Hadwiger und Edward Nelson benanntes Problem der Geometrischen Graphentheorie. Gesucht wird die minimal benötigte Anzahl an Farben, um eine Ebene derart einzufärben, dass jeweils zwei Punkte mit… …   Deutsch Wikipedia

  • Hadwiger — ist der Familienname folgender Personen: Victor Hadwiger (1878–1911), deutscher Schriftsteller Helmut Hadwiger (1922–2004), österreichischer Skispringer Hugo Hadwiger (1908–1981), deutscher Mathematiker Siehe auch: Hadwigers Vermutung… …   Deutsch Wikipedia

  • Hugo Hadwiger — (1908 ndash; 1981) was a Swiss mathematician. He is known for Hadwiger s theorem in integral geometry, and a number of conjectures. He also worked on a Swiss enhancement of the Enigma cipher machine, known as NEMA.His 1957 book Vorlesungen über… …   Wikipedia

  • Four color theorem — Example of a four colored map A four colori …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • De Bruijn–Erdős theorem (graph theory) — This article is about coloring infinite graphs. For the number of lines determined by a finite set of points, see De Bruijn–Erdős theorem (incidence geometry). In graph theory, the De Bruijn–Erdős theorem, proved by Nicolaas Govert de Bruijn and… …   Wikipedia

  • Unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Millennium Prize Problems Of the seven Millennium Prize Problems set by the Clay Mathematics Institute, the six ones yet to be solved are:… …   Wikipedia

  • Leo Moser — Pour les articles homonymes, voir Moser.  Ne doit pas être confondu avec le mathématicien allemand Jürgen K. Moser. Leo Moser (11 avril 1921 9 février 1970) était un mathématicien austro canadien. On le connait entre autres pour la notation… …   Wikipédia en Français

  • Открытые математические проблемы — Открытые (нерешённые) математические проблемы  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна… …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”