Difference between revisions of "Hadwiger-Nelson problem"

From Polymath1Wiki
Jump to: navigation, search
(Notable unit distance graphs)
(3 intermediate revisions by the same user not shown)
Line 10: Line 10:
 
| 7
 
| 7
 
| 11
 
| 11
| Two 60-120-60-120 rhombi with a common vertex, joined at the opposing vertices
+
| Two 60-120-60-120 rhombi with a common vertex, with one pair of sharp vertices coincident and the other joined
 
| Not 3-colorable
 
| Not 3-colorable
 
|-
 
|-
Line 21: Line 21:
 
| [https://arxiv.org/abs/1804.02385 J]
 
| [https://arxiv.org/abs/1804.02385 J]
 
| 31
 
| 31
|
+
| 72
 
| Contains 13 copies of H  
 
| Contains 13 copies of H  
 
| Has essentially six 4-colorings in which no H has a monochromatic triangle
 
| Has essentially six 4-colorings in which no H has a monochromatic triangle
Line 27: Line 27:
 
| [https://arxiv.org/abs/1804.02385 K]
 
| [https://arxiv.org/abs/1804.02385 K]
 
| 61
 
| 61
|
+
| 150
 
| Contains 2 copies of J
 
| Contains 2 copies of J
| In all 4-colorings without an H with a monochromatic triangle, all linking edges are monochromatic
+
| In all 4-colorings lacking an H with a monochromatic triangle, all pairs of vertices at distance 4 are monochromatic
 
|-
 
|-
 
| [https://arxiv.org/abs/1804.02385 L]
 
| [https://arxiv.org/abs/1804.02385 L]
 
| 121
 
| 121
|
+
| 301
 
| Contains two copies of K and 52 copies of H
 
| Contains two copies of K and 52 copies of H
| all 4-colorings contain an H with a monochromatic triangle
+
| All 4-colorings contain an H with a monochromatic triangle
 
|-
 
|-
 
| [https://arxiv.org/abs/1804.02385 T]
 
| [https://arxiv.org/abs/1804.02385 T]
Line 41: Line 41:
 
| 15
 
| 15
 
| Contains one Moser spindle and useful symmetry
 
| Contains one Moser spindle and useful symmetry
|
+
| Three vertices form an equilateral triangle
 
|-
 
|-
 
| [https://arxiv.org/abs/1804.02385 U]
 
| [https://arxiv.org/abs/1804.02385 U]
 
| 15
 
| 15
|
+
| 33
 +
| Three copies of T at 120-degree rotations
 
| Contains three Moser spindles
 
| Contains three Moser spindles
|
 
 
|-
 
|-
 
| [https://arxiv.org/abs/1804.02385 V]
 
| [https://arxiv.org/abs/1804.02385 V]
 
| 31
 
| 31
|
+
| 30
 
| Unit vectors at angles consistent with three interlocking Moser spindles
 
| Unit vectors at angles consistent with three interlocking Moser spindles
 
|
 
|
Line 57: Line 57:
 
| [https://arxiv.org/abs/1804.02385 W]
 
| [https://arxiv.org/abs/1804.02385 W]
 
| 301
 
| 301
|
+
| 1230
 
| Cartesian product of V with itself, minus vertices at \sqrt(3) from the centre
 
| Cartesian product of V with itself, minus vertices at \sqrt(3) from the centre
 
|
 
|
Line 63: Line 63:
 
| [https://arxiv.org/abs/1804.02385 M]
 
| [https://arxiv.org/abs/1804.02385 M]
 
| 1345
 
| 1345
|
+
| 8268
| Cartesian product of W and H, all 4-colorings have a monochromatic triangle in the central copy of H
+
| Cartesian product of W and H
 +
| All 4-colorings have a monochromatic triangle in the central copy of H
 +
|
 
|-
 
|-
 
| [https://arxiv.org/abs/1804.02385 N]
 
| [https://arxiv.org/abs/1804.02385 N]
 
| 20425
 
| 20425
 +
| 151311
 +
| Contains 52 copies of M arranged around the H-copies of L
 +
| Not 4-colorable
 
|
 
|
| Contains 52 copies of M arranged around the H-copies of L; not 4-colorable
+
|-
 +
| [https://arxiv.org/abs/1804.02385 G]
 +
| 1581
 +
| 7877
 +
| N "shrunk" by stepwise deletions and replacements of vertices
 +
| Not 4-colorable
 
|}
 
|}
  

Revision as of 11:48, 14 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 60-120-60-120 rhombi with a common vertex, with one pair of sharp vertices coincident and the other joined Not 3-colorable
H 7 12 Vertices and center of a hexagon Has essentially four 4-colorings, two of which contain a monochromatic triangle
J 31 72 Contains 13 copies of H Has essentially six 4-colorings in which no H has a monochromatic triangle
K 61 150 Contains 2 copies of J In all 4-colorings lacking an H with a monochromatic triangle, all pairs of vertices at distance 4 are monochromatic
L 121 301 Contains two copies of K and 52 copies of H All 4-colorings contain an H with a monochromatic triangle
T 9 15 Contains one Moser spindle and useful symmetry Three vertices form an equilateral triangle
U 15 33 Three copies of T at 120-degree rotations Contains three Moser spindles
V 31 30 Unit vectors at angles consistent with three interlocking Moser spindles
W 301 1230 Cartesian product of V with itself, minus vertices at \sqrt(3) from the centre
M 1345 8268 Cartesian product of W and H All 4-colorings have a monochromatic triangle in the central copy of H
N 20425 151311 Contains 52 copies of M arranged around the H-copies of L Not 4-colorable
G 1581 7877 N "shrunk" by stepwise deletions and replacements of vertices 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.