Hadwiger–Nelson problem

Last updated April 11, 2024

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?

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]

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.

One application of the problem connects it to the Beckman–Quarles theorem, according to which any mapping of the Euclidean plane (or any higher dimensional space) to itself that preserves unit distances must be an isometry, preserving all distances.^[2] Finite colorings of these spaces can be used to construct mappings from them to higher-dimensional spaces that preserve distances but are not isometries. For instance, the Euclidean plane can be mapped to a six-dimensional space by coloring it with seven colors so that no two points at distance one have the same color, and then mapping the points by their colors to the seven vertices of a six-dimensional regular simplex with unit-length edges. This maps any two points at unit distance to distinct colors, and from there to distinct vertices of the simplex, at unit distance apart from each other. However, it maps all other distances to zero or one, so it is not an isometry. If the number of colors needed to color the plane could be reduced from seven to a lower number, the same reduction would apply to the dimension of the target space in this construction.^[3]

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.^[4]

The lower bound was raised to five in 2018, when computer scientist and biologist Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph. The proof is computer assisted.^[5] Mathematician Gil Kalai and computer scientist Scott Aaronson 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.^[6] As of 2021, the smallest known unit distance graph with chromatic number 5 has 509 vertices.^[7] 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

The problem can easily be extended to higher dimensions. Finding the chromatic number of 3-space is a particularly interesting problem. 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.^[8]

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 $\lfloor 2+{\sqrt {n}}\rfloor ^{n}$ . A lower bound from simplexes is $n+1$ . For $n>1$ , a lower bound of $n+2$ is available using a generalization of the Moser spindle: a pair of the objects (each two simplexes glued together on a facet) which are joined on one side by a point and the other side by a line. An exponential lower bound was proved by Frankl and Wilson in 1981.^[9]

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.^[10] 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.^[11]

Notes

↑ Soifer (2008), pp. 557–563; Shelah & Soifer (2003).
↑ Beckman & Quarles (1953).
↑ Rassias (2001).
↑ Soifer (2008), p. 19.
↑ de Grey (2018).
↑ Kalai (2018); Aaronson (2018)
↑ Mixon (2021).
↑ Coulson (2002); Radoičić & Tóth (2003).
↑ Frankl & Wilson (1981).
↑ See, e.g., Croft, Falconer & Guy (1991).
↑ Woodall (1973); see also Coulson (2004) for a different proof of a similar result.

Related Research Articles

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary of non-zero length. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubts remain.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

<span class="mw-page-title-main">Hugo Hadwiger</span> Swiss mathematician (1908–1981)

Hugo Hadwiger was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

In graph theory, the Hadwiger conjecture states that if $is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.$

In graph theory, the Hadwiger number of an undirected graph $G$ is the size of the largest complete graph that can be obtained by contracting edges of $G$ . Equivalently, the Hadwiger number $h (G)$ is the largest number $n$ for which the complete graph $K n$ is a minor of $G$ , a smaller graph obtained from $G$ by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of $G$ or the homomorphism degree of $G$ . It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of $G$ .

In mathematics, 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 whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

In geometry, the Beckman–Quarles theorem states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all Euclidean distances. Equivalently, every homomorphism from the unit distance graph of the plane to itself must be an isometry of the plane. The theorem is named after Frank S. Beckman and Donald A. Quarles Jr., who published this result in 1953; it was later rediscovered by other authors and re-proved in multiple ways. Analogous theorems for rational subsets of Euclidean spaces, or for non-Euclidean geometry, are also known.

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. It is a unit distance graph requiring four colors in any graph coloring, and its existence can be used to prove that the chromatic number of the plane is at least four.

In graph theory, a branch of mathematics, a crown graph on $2 n$ vertices is an undirected graph with two sets of vertices ${u 1, u 2, \dots, u n}$ and ${v 1, v 2, \dots, v n}$ and with an edge from $u i$ to $v j$ whenever $i \neq j$ .

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.$

In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor at Smith College, who stated it as a conjecture in 2007; it is one of his many conjectures in graph coloring theory. The conjecture states that, among all graphs requiring $colors, the complete graph is the one with the smallest crossing number. Equivalently, if a graph can be drawn with fewer crossings than, then, according to the conjecture, it may be colored with fewer than colors.$

In mathematics, and particularly in graph theory, the dimension of a graph is the least integer $n$ such that there exists a "classical representation" of the graph in the Euclidean space of dimension $n$ with all the edges having unit length.

In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it as a unit distance graph that requires four colors in any graph coloring. Thus, like the simpler Moser spindle, it provides a lower bound for the Hadwiger–Nelson problem: coloring the points of the Euclidean plane so that each unit line segment has differently-colored endpoints requires at least four colors.

The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators is a book on graph coloring, Ramsey theory, and the history of development of these areas, concentrating in particular on the Hadwiger–Nelson problem and on the biography of Bartel Leendert van der Waerden. It was written by Alexander Soifer and published by Springer-Verlag in 2009 (ISBN 978-0-387-74640-1).

References

Aaronson, Scott (April 11, 2018), Amazing progress on longstanding open problems
Beckman, F. S.; Quarles, D. A. Jr. (1953), "On isometries of Euclidean spaces", Proceedings of the American Mathematical Society , 4 (5): 810–815, doi: 10.2307/2032415 , JSTOR 2032415, MR 0058193
de Bruijn, N. G.; Erdős, P. (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A, 54: 371–373, CiteSeerX 10.1.1.210.6623 , doi:10.1016/S1385-7258(51)50053-7
Chilakamarri, K. B. (1993), "The unit-distance graph problem: a brief survey and some new results", Bull Inst. Combin. Appl., 8: 39–60
Chilakamarri, Kiran B.; Mahoney, Carolyn R. (1996), "Unit-distance graphs, graphs on the integer lattice and a Ramsey type result", Aequationes Mathematicae , 51 (1–2): 48–67, doi:10.1007/BF01831139, MR 1372782, S2CID 189831504
Coulson, D. (2004). "On the chromatic number of plane tilings". Journal of the Australian Mathematical Society. 77 (2). Cambridge University Press (CUP): 191–196. doi: 10.1017/s1446788700013574 . ISSN 1446-7887.
Coulson, D. (2002), "A 15-colouring of 3-space omitting distance one", Discrete Math., 256 (1–2): 83–90, doi:10.1016/S0012-365X(01)00183-2
Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1991), Unsolved Problems in Geometry, Springer-Verlag, Problem G10, ISBN 978-0-387-97506-1
Frankl, P.; Wilson, R.M. (1981), "Intersection theorems with geometric consequences", Combinatorica, 1 (4): 357–368, doi:10.1007/BF02579457, S2CID 6768348
Gardner, Martin (October 1960), "A new collection of 'brain-teasers'", Mathematical Games, Scientific American , 203 (4): 180, doi:10.1038/scientificamerican1060-218, JSTOR 24940666 {{citation}}: CS1 maint: date and year (link)
de Grey, Aubrey D.N.J. (2018), "The Chromatic Number of the Plane Is at least 5", Geombinatorics, 28: 5–18, arXiv: 1804.02385 , Bibcode:2016arXiv160407134W, MR 3820926
Hadwiger, Hugo (1945), "Überdeckung des euklidischen Raumes durch kongruente Mengen", Portugal. Math., 4: 238–242
Hadwiger, Hugo (1961), "Ungelöste Probleme No. 40", Elem. Math., 16: 103–104
Heule, Marijn J.H. (2018), Computing Small Unit-Distance Graphs with Chromatic Number 5, arXiv: 1805.12181 , Bibcode:2018arXiv180512181H
Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization, pp. 150–152, ISBN 978-0-471-02865-9
Kalai, Gil (April 10, 2018), Aubrey de Grey: The chromatic number of the plane is at least 5
Mixon, Dustin (February 1, 2021), Polymath16, seventeenth thread: Declaring victory , retrieved 16 August 2021
Polymath, D. H. J. (April 2018), Hadwiger-Nelson problem (Polymath project page), archived from the original on 2022-02-16
Radoičić, Radoš; Tóth, Géza (2003), "Note on the chromatic number of the space", in Aronov, Boris; Basu, Saugata; Pach, Janos; Sharir, Micha (eds.), Discrete and Computational Geometry: The Goodman–Pollack Festschrift (PDF), Algorithms and Combinatorics, vol. 25, Berlin: Springer, pp. 695–698, doi:10.1007/978-3-642-55566-4_32, ISBN 978-3-540-00371-7, MR 2038498
Rassias, Themistocles M. (2001), "Isometric mappings and the problem of A. D. Aleksandrov for conservative distances", in Florian, H.; Ortner, N.; Schnitzer, F. J.; Tutschke, W. (eds.), Functional-Analytic and Complex Methods, their Interactions, and Applications to Partial Differential Equations: Proceedings of the International Workshop held at Graz University Of Technology, Graz, February 12–16, 2001, River Edge, New Jersey: World Scientific Publishing Co., Inc., pp. 118–125, doi:10.1142/4822, ISBN 978-981-02-4764-5, MR 1893253
Shelah, Saharon; Soifer, Alexander (2003), "Axiom of choice and chromatic number of the plane", Journal of Combinatorial Theory, Series A, 103 (2): 387–391, doi:10.1016/S0097-3165(03)00102-X
Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, ISBN 978-0-387-74640-1
Woodall, D. R. (1973), "Distances realized by sets covering the plane", Journal of Combinatorial Theory , Series A, 14 (2): 187–200, doi: 10.1016/0097-3165(73)90020-4 , MR 0310770

External links

O'Rourke, Joseph, "Problem 57: Chromatic Number of the Plane", The Open Problems Project
Mohar, Bojan (2001), The chromatic number of the Unit Distance Graph
Kalai, Gil (2018), Coloring Problems for Arrangements of Circles (and Pseudocircles)
Grime, James (February 27, 2019), "A Colorful Unsolved Problem", Numberphile, archived from the original on 2021-12-21

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Soifer (2008), pp. 557–563; Shelah & Soifer (2003).

[FOOTNOTEBeckmanQuarles1953-2] Beckman & Quarles (1953).

[FOOTNOTERassias2001-3] Rassias (2001).

[FOOTNOTESoifer200819-4] Soifer (2008), p. 19.

[FOOTNOTEde_Grey2018-5] Grey (2018).

[6] Kalai (2018); Aaronson (2018)

[FOOTNOTEMixon2021-7] Mixon (2021).

[8] Coulson (2002); Radoičić & Tóth (2003).

[FOOTNOTEFranklWilson1981-9] Frankl & Wilson (1981).

[10] See, e.g., Croft, Falconer & Guy (1991).

[11] Woodall (1973); see also Coulson (2004) for a different proof of a similar result.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]