Difference between revisions of "Hadwiger-Nelson problem"

From Polymath Wiki
Jump to: navigation, search
(Bibliography)
Line 1: Line 1:
The Chromatic Number of the Plane (CNP) is the chromatic number of the graph whose vertices are elements of the plane, and two points are connected by an edge if they are a unit distance apart.  The Hadwiger-Nelson problem asks to compute CNP.  The bounds <math>4 \leq CNP \leq 7</math> are classical; recently [deG2018] it was shown that <math>CNP \geq 5</math>.
+
The Chromatic Number of the Plane (CNP) is the chromatic number of the graph whose vertices are elements of the plane, and two points are connected by an edge if they are a unit distance apart.  The Hadwiger-Nelson problem asks to compute CNP.  The bounds <math>4 \leq CNP \leq 7</math> are classical; recently [deG2018] it was shown that <math>CNP \geq 5</math>.  This is achieved by explicitly locating finite unit distance graphs with chromatic number at least 5.
  
 +
== Notable unit distance graphs ==
 +
 +
{| border=1
 +
|-
 +
!Name!!Number of vertices!! Number of edges !! Structure !! Colorings
 +
|-
 +
| Moser spindle
 +
| 7
 +
| 11
 +
| Two rhombi with a common vertex, joined at the opposing vertices
 +
| No 3-colorings
 +
|-
 +
| H
 +
| 7
 +
| 12
 +
| Vertices and center of a hexagon
 +
| Has essentially four 4-colorings, two of which contain a monochromatic triangle
 +
|-
 +
| J
 +
| 31
 +
|
 +
| Contains 13 copies of H
 +
| Has essentially six 4-colorings in which no H has a monochromatic triangle
 +
|-
 +
| K
 +
| 61
 +
|
 +
| Contains 2 copies of J
 +
| In all 4-colorings without an H with a monochromatic triangle, all linking edges are monochromatic
 +
|-
 +
| L
 +
| 121
 +
|
 +
| Contains two copies of K and 52 copies of H
 +
| all 4-colorings contain an H with a monochromatic triangle
 +
|-
 +
| T
 +
| 9
 +
| 15
 +
| Contains two Moser spindles
 +
|
 +
|-
 +
| U
 +
| 15
 +
|
 +
| Contains three Moser spindles
 +
|
 +
|-
 +
| V
 +
| 30
 +
|
 +
|
 +
|
 +
|-
 +
| W
 +
| 301
 +
|
 +
| Built using V
 +
|
 +
|-
 +
| M
 +
| 1345
 +
|
 +
| Contains one copy of H and 7 copies of W
 +
| All 4-colorings have a monochromatic triangle in H
 +
|-
 +
| N
 +
| 20425
 +
|
 +
|
 +
| Not 4-colorable
 +
|}
  
  
Line 22: Line 94:
 
== Wikipedia ==
 
== Wikipedia ==
  
 +
* [https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory) de Bruijn-Erdos theorem]
 
* [https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem Hadwiger-Nelson problem]
 
* [https://en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem Hadwiger-Nelson problem]
 
* [https://en.wikipedia.org/wiki/Lov%C3%A1sz_number Lovasz number]
 
* [https://en.wikipedia.org/wiki/Lov%C3%A1sz_number Lovasz number]
Line 28: Line 101:
 
== Bibliography ==
 
== Bibliography ==
  
* [deG2018] A. de Grey, [[https://arxiv.org/abs/1804.02385 The chromatic number of the plane is  at least 5]], arXiv:1804.02385
+
* [deBE1951] N. G. de Bruijn, P. Erdős, [http://www.math-inst.hu/~p_erdos/1951-01.pdf A colour problem for infinite graphs and a problem in the theory of relations], Nederl. Akad. Wetensch. Proc. Ser. A, 54 (1951): 371–373, MR 0046630.
* [H1945] H. Hadwiger, Uberdeckung des euklidischen Raum durch kongruente Mengen, PortugaliaeMath. 4 (1945), 238–242.
+
 
 +
* [deG2018] A. de Grey, [https://arxiv.org/abs/1804.02385 The chromatic number of the plane is  at least 5], arXiv:1804.02385
 +
* [H1945] H. Hadwiger, Uberdeckung des euklidischen Raum durch kongruente Mengen, Portugaliae Math. 4 (1945), 238–242.
 
* [MM1961] L. Moser and M. Moser, Solution to Problem 10, Can. Math. Bull. 4 (1961), 187–189.
 
* [MM1961] L. Moser and M. Moser, Solution to Problem 10, Can. Math. Bull. 4 (1961), 187–189.
 
* [P1998] D. Pritikin, All unit-distance graphs of order 6197 are 6-colorable, Journal of Combinatorial Theory, Series B 73.2 (1998): 159-163.
 
* [P1998] D. Pritikin, All unit-distance graphs of order 6197 are 6-colorable, Journal of Combinatorial Theory, Series B 73.2 (1998): 159-163.
 
* [S2008] A. Soifer, The Mathematical Coloring Book, Springer, 2008, ISBN-13: 978-0387746401.
 
* [S2008] A. Soifer, The Mathematical Coloring Book, Springer, 2008, ISBN-13: 978-0387746401.

Revision as of 20:37, 13 April 2018

The Chromatic Number of the Plane (CNP) is the chromatic number of the graph whose vertices are elements of the plane, and two points are connected by an edge if they are a unit distance apart. The Hadwiger-Nelson problem asks to compute CNP. The bounds [math]4 \leq CNP \leq 7[/math] are classical; recently [deG2018] it was shown that [math]CNP \geq 5[/math]. This is achieved by explicitly locating finite unit distance graphs with chromatic number at least 5.

Notable unit distance graphs

Name Number of vertices Number of edges Structure Colorings
Moser spindle 7 11 Two rhombi with a common vertex, joined at the opposing vertices No 3-colorings
H 7 12 Vertices and center of a hexagon Has essentially four 4-colorings, two of which contain a monochromatic triangle
J 31 Contains 13 copies of H Has essentially six 4-colorings in which no H has a monochromatic triangle
K 61 Contains 2 copies of J In all 4-colorings without an H with a monochromatic triangle, all linking edges are monochromatic
L 121 Contains two copies of K and 52 copies of H all 4-colorings contain an H with a monochromatic triangle
T 9 15 Contains two Moser spindles
U 15 Contains three Moser spindles
V 30
W 301 Built using V
M 1345 Contains one copy of H and 7 copies of W All 4-colorings have a monochromatic triangle in H
N 20425 Not 4-colorable


Blog posts and other online forums

Code and data

Wikipedia

Bibliography

  • [deG2018] A. de Grey, The chromatic number of the plane is at least 5, arXiv:1804.02385
  • [H1945] H. Hadwiger, Uberdeckung des euklidischen Raum durch kongruente Mengen, Portugaliae Math. 4 (1945), 238–242.
  • [MM1961] L. Moser and M. Moser, Solution to Problem 10, Can. Math. Bull. 4 (1961), 187–189.
  • [P1998] D. Pritikin, All unit-distance graphs of order 6197 are 6-colorable, Journal of Combinatorial Theory, Series B 73.2 (1998): 159-163.
  • [S2008] A. Soifer, The Mathematical Coloring Book, Springer, 2008, ISBN-13: 978-0387746401.