Hadwiger-Nelson problem: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
No edit summary
Line 26: Line 26:


Another basic operation is '''spindling''': taking two copies of a graph <math>G</math>, gluing them together at one vertex, and rotating the copies so that the two copies of another vertex are a unit distance apart.  For instance, the Moser spindle is the spindling of a rhombus graph.  If a graph has two vertices forced to be the same color in a k-coloring, then the spindling of that graph at those two vertices is not k-colorable.
Another basic operation is '''spindling''': taking two copies of a graph <math>G</math>, gluing them together at one vertex, and rotating the copies so that the two copies of another vertex are a unit distance apart.  For instance, the Moser spindle is the spindling of a rhombus graph.  If a graph has two vertices forced to be the same color in a k-coloring, then the spindling of that graph at those two vertices is not k-colorable.
Many of the graphs are embeddable in abelian groups or rings, particularly those generated by the roots of unity <math>\omega_t := \exp( i \arccos( 1 - \frac{2t} ))</math> for various natural numbers t.


{| border=1
{| border=1
|-
|-
!Name!!Number of vertices!! Number of edges !! Structure !! Colorings  
!Name!!Number of vertices!! Number of edges !! Structure !! Group !! Colorings  
|-
|-
| [https://en.wikipedia.org/wiki/Moser_spindle Moser spindle]  
| [https://en.wikipedia.org/wiki/Moser_spindle Moser spindle]  
Line 35: Line 37:
| 11
| 11
| Two 60-120-60-120 rhombi with a common vertex, with one pair of sharp vertices coincident and the other joined
| Two 60-120-60-120 rhombi with a common vertex, with one pair of sharp vertices coincident and the other joined
| <math>{\bf Z}[\omega_1, \omega_3]</math>
| Not 3-colorable
| Not 3-colorable
|-
|-
Line 41: Line 44:
| 18
| 18
| Contains the center and vertices of a hexagon and equilateral triangle
| Contains the center and vertices of a hexagon and equilateral triangle
| <math>{\bf Z}[\omega_1, \omega_3]</math>
| Not 3-colorable
| Not 3-colorable
|-
|-
Line 47: Line 51:
| 12
| 12
| Vertices and center of a hexagon
| Vertices and center of a hexagon
|  <math>{\bf Z}[\omega_1]</math>
| Has essentially four 4-colorings, two of which contain a monochromatic triangle
| Has essentially four 4-colorings, two of which contain a monochromatic triangle
|-
|-
Line 53: Line 58:
| 72
| 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 59: Line 65:
| 150
| 150
| Contains 2 copies of J
| 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
| In all 4-colorings lacking an H with a monochromatic triangle, all pairs of vertices at distance 4 are monochromatic
|-
|-
Line 65: Line 72:
| 301
| 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
|-
|-
Line 71: Line 79:
|
|
| Has 40 copies of H
| Has 40 copies of H
|
| All 4-colorings contain an H with a monochromatic triangle
| All 4-colorings contain an H with a monochromatic triangle
|-
|-
Line 76: Line 85:
| 120
| 120
| 354
| 354
|
|
|
| All 4-colorings contain an H with a monochromatic triangle
| All 4-colorings contain an H with a monochromatic triangle
Line 84: Line 94:
| Contains one Moser spindle and useful symmetry; three vertices form an equilateral triangle
| 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]
Line 90: Line 101:
| Three copies of T at 120-degree rotations: <math>T \cup \mathrm{rot}(T, 2\pi/3) \cup \mathrm{rot}(T, 4\pi/3)</math>
| Three copies of T at 120-degree rotations: <math>T \cup \mathrm{rot}(T, 2\pi/3) \cup \mathrm{rot}(T, 4\pi/3)</math>
|  
|  
|
|-
|-
| [https://arxiv.org/abs/1804.02385 V]
| [https://arxiv.org/abs/1804.02385 V]
Line 95: Line 107:
| 30
| 30
| Unit vectors at angles consistent with three interlocking Moser spindles
| Unit vectors at angles consistent with three interlocking Moser spindles
|
|
|
|-
|-
Line 101: Line 114:
| 60
| 60
| Union of V and a rotation of V: <math>V \cup \mathrm{rot}(V, \mathrm{arccos}(7/8))</math>
| Union of V and a rotation of V: <math>V \cup \mathrm{rot}(V, \mathrm{arccos}(7/8))</math>
|
|
|
|-
|-
Line 107: Line 121:
| 24
| 24
| Star graph
| Star graph
|
|
|
|-
|-
Line 113: Line 128:
| 24
| 24
| Star graph
| Star graph
|
|
|
|-
|-
Line 119: Line 135:
| 12
| 12
| Subgraph of <math>V_a</math>
| Subgraph of <math>V_a</math>
|
|
|
|-
|-
Line 125: Line 142:
|
|
| Subgraph of <math>V_a</math>; shares a line of symmetry with <math>V_a</math>
| Subgraph of <math>V_a</math>; shares a line of symmetry with <math>V_a</math>
|
|
|
|-
|-
Line 131: Line 149:
| 12
| 12
| Subgraph of <math>V_b</math>
| Subgraph of <math>V_b</math>
|
|
|
|-
|-
Line 137: Line 156:
| 36
| 36
| Unit vectors with angles <math>i \frac{\pi}{3} + j \mathrm{arccos} \frac{5}{6} + k \mathrm{arccos} \frac{7}{8}</math>
| Unit vectors with angles <math>i \frac{\pi}{3} + j \mathrm{arccos} \frac{5}{6} + k \mathrm{arccos} \frac{7}{8}</math>
|
|
|
|-
|-
Line 143: Line 163:
| 1230
| 1230
| Cartesian product of V with itself, minus vertices at more than <math>\sqrt{3}</math> from the centre (i.e. <math>\mathrm{trim}(V \oplus V, \sqrt{3})</math>)
| Cartesian product of V with itself, minus vertices at more than <math>\sqrt{3}</math> from the centre (i.e. <math>\mathrm{trim}(V \oplus V, \sqrt{3})</math>)
|
|  
|  
|-
|-
Line 149: Line 170:
|
|
| Trimmed product of V with itself (<math>\mathrm{trim}(V \oplus V, 1.95)</math>)
| Trimmed product of V with itself (<math>\mathrm{trim}(V \oplus V, 1.95)</math>)
|
|
|
|-
|-
Line 155: Line 177:
| 8268
| 8268
| Cartesian product of W and H (<math>W \oplus H</math>)
| Cartesian product of W and H (<math>W \oplus H</math>)
| <math>{\bf Z}[\omega_1, \omega_3]</math>
| All 4-colorings have a monochromatic triangle in the central copy of H
| All 4-colorings have a monochromatic triangle in the central copy of H
|-
|-
Line 161: Line 184:
|
|
| Deleting vertices from M while maintaining its restriction on H
| Deleting vertices from M while maintaining its restriction on H
|
| All 4-colorings have a monochromatic triangle in the central copy of H
| All 4-colorings have a monochromatic triangle in the central copy of H
|-
|-
Line 167: Line 191:
|
|
| Sum of H with a trimmed product of <math>V_1</math> with itself  
| Sum of H with a trimmed product of <math>V_1</math> with itself  
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 173: Line 198:
| 151311
| 151311
| Contains 52 copies of M arranged around the H-copies of L
| Contains 52 copies of M arranged around the H-copies of L
|  <math>{\bf Z}[\omega_1, \omega_3, \omega_4, \omega_{16}]</math>
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 179: Line 205:
| 7909
| 7909
| N "shrunk" by stepwise deletions and replacements of vertices
| N "shrunk" by stepwise deletions and replacements of vertices
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 185: Line 212:
| 7877
| 7877
| Deleting 4 vertices from <math>G_0</math>
| Deleting 4 vertices from <math>G_0</math>
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 191: Line 219:
|
|
| Deleting 8 vertices from <math>G_0</math>
| Deleting 8 vertices from <math>G_0</math>
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 197: Line 226:
| 4461
| 4461
| Juxtaposing two copies of M and shrinking
| Juxtaposing two copies of M and shrinking
|  <math>{\bf Z}[\omega_1, \omega_3, \omega_4]</math>
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 202: Line 232:
| 826
| 826
| 4273
| 4273
|
|
|
| Not 4-colorable
| Not 4-colorable
Line 208: Line 239:
| '''803'''
| '''803'''
| 4144  
| 4144  
|
|
|
| Not 4-colorable
| Not 4-colorable
Line 215: Line 247:
|
|
| Union of <math>W_1</math> and a rotated copy of <math>W_1</math>
| Union of <math>W_1</math> and a rotated copy of <math>W_1</math>
|
|
|
|-
|-
Line 221: Line 254:
|
|
| Trimmed sum of R and H
| Trimmed sum of R and H
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 227: Line 261:
|
|
|
|
| Has two vertices forced to be the same color in a 4-coloring
|  <math>{\bf Z}[\omega_1, \omega_3, \omega_{64/9}]</math>
| Has two vertices forced to be the same color in a 4-coloring; also no monochromatic triangles
|-
|-
| [[https://dustingmixon.wordpress.com/2018/04/22/polymath16-second-thread-what-does-it-take-to-be-5-chromatic/#comment-4074 No name assigned]
| [[https://dustingmixon.wordpress.com/2018/04/22/polymath16-second-thread-what-does-it-take-to-be-5-chromatic/#comment-4074 No name assigned]
Line 233: Line 268:
|
|
| Subgraph of <math>V \oplus V \oplus H</math>
| Subgraph of <math>V \oplus V \oplus H</math>
|
| Has two vertices forced to be the same color in a 4-coloring
| Has two vertices forced to be the same color in a 4-coloring
|-
|-
Line 239: Line 275:
|
|
|  
|  
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 245: Line 282:
|
|
|  
|  
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 251: Line 289:
|
|
| Trimmed version of <math>V_a \oplus V_x \oplus H \cup V_b \oplus V_y \oplus H</math>
| Trimmed version of <math>V_a \oplus V_x \oplus H \cup V_b \oplus V_y \oplus H</math>
|
| Not 4-colorable
| Not 4-colorable
|-
|-
Line 257: Line 296:
| 44439
| 44439
|
|
|  <math>{\bf Z}[\omega_1, \omega_3, \omega_4]</math>
| Not 4-colorable
| Not 4-colorable
|}
|}

Revision as of 19:19, 2 May 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]\displaystyle{ 4 \leq CNP \leq 7 }[/math] are classical; recently [deG2018] it was shown that [math]\displaystyle{ CNP \geq 5 }[/math]. This is achieved by explicitly locating finite unit distance graphs with chromatic number at least 5.

The Polymath16 project seeks to simplify the graphs used in [deG2018] to establish this lower bound. More precisely, the goals are

  • Goal 1: Find progressively smaller 5-chromatic unit-distance graphs.
  • Goal 2: Reduce (ideally to zero) the reliance on computer assistance for the proof. Computer assistance was leveraged in [deG2018] to analyze a subgraph of size 397.
  • Goal 3: Apply these simpler graphs to inform progress in related areas. For example:
    • Find a 6-chromatic unit-distance graph.
    • Improve the corresponding bound in higher dimensions.
    • Improve the current record of 105/29 for the fractional chromatic number of the plane.
    • Find the smallest unit-distance graph of a given minimum degree (excluding, in some natural way, boring cases like Cartesian products of a graph with a hypercube).


Polymath threads

Notable unit distance graphs

A unit distance graph is a graph that can be realised as a collection of vertices in the plane, with two vertices connected by an edge if they are precisely a unit distance apart. The chromatic number of any such graph is a lower bound for [math]\displaystyle{ CNP }[/math]; in particular, if one can find a unit distance graph with no 4-colorings, then [math]\displaystyle{ CNP \geq 5 }[/math]. The boldface number of vertices is the current minimal number of vertices of a unit distance graph that is currently known to not be 4-colorable.

[math]\displaystyle{ G_1 \oplus G_2 }[/math] denotes the Minkowski sum of two unit distance graphs [math]\displaystyle{ G_1,G_2 }[/math] (vertices in [math]\displaystyle{ G_1 \oplus G_2 }[/math] are sums of the vertices of [math]\displaystyle{ G_1,G_2 }[/math]). [math]\displaystyle{ G_1 \cup G_2 }[/math] denotes the union. [math]\displaystyle{ \mathrm{rot}(G, \theta) }[/math] denotes [math]\displaystyle{ G }[/math] rotated counterclockwise by [math]\displaystyle{ \theta }[/math]. [math]\displaystyle{ \mathrm{trim}(G,r) }[/math] denotes the trimming of [math]\displaystyle{ G }[/math] after removing all vertices of distance greater than [math]\displaystyle{ r }[/math] from the origin.

Another basic operation is spindling: taking two copies of a graph [math]\displaystyle{ G }[/math], gluing them together at one vertex, and rotating the copies so that the two copies of another vertex are a unit distance apart. For instance, the Moser spindle is the spindling of a rhombus graph. If a graph has two vertices forced to be the same color in a k-coloring, then the spindling of that graph at those two vertices is not k-colorable.

Many of the graphs are embeddable in abelian groups or rings, particularly those generated by the roots of unity [math]\displaystyle{ \omega_t := \exp( i \arccos( 1 - \frac{2t} )) }[/math] for various natural numbers t.

Name Number of vertices Number of edges Structure Group 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 [math]\displaystyle{ {\bf Z}[\omega_1, \omega_3] }[/math] Not 3-colorable
Golomb graph 10 18 Contains the center and vertices of a hexagon and equilateral triangle [math]\displaystyle{ {\bf Z}[\omega_1, \omega_3] }[/math] Not 3-colorable
H 7 12 Vertices and center of a hexagon [math]\displaystyle{ {\bf Z}[\omega_1] }[/math] 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
[math]\displaystyle{ L_1 }[/math] 97 Has 40 copies of H All 4-colorings contain an H with a monochromatic triangle
[math]\displaystyle{ L_2 }[/math] 120 354 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: [math]\displaystyle{ T \cup \mathrm{rot}(T, 2\pi/3) \cup \mathrm{rot}(T, 4\pi/3) }[/math]
V 31 30 Unit vectors at angles consistent with three interlocking Moser spindles
[math]\displaystyle{ V_1 }[/math] 61 60 Union of V and a rotation of V: [math]\displaystyle{ V \cup \mathrm{rot}(V, \mathrm{arccos}(7/8)) }[/math]
[math]\displaystyle{ V_a }[/math] 25 24 Star graph
[math]\displaystyle{ V_b }[/math] 25 24 Star graph
[math]\displaystyle{ V_x }[/math] 13 12 Subgraph of [math]\displaystyle{ V_a }[/math]
[math]\displaystyle{ V_z }[/math] Subgraph of [math]\displaystyle{ V_a }[/math]; shares a line of symmetry with [math]\displaystyle{ V_a }[/math]
[math]\displaystyle{ V_y }[/math] 13 12 Subgraph of [math]\displaystyle{ V_b }[/math]
[math]\displaystyle{ V_A }[/math] 37 36 Unit vectors with angles [math]\displaystyle{ i \frac{\pi}{3} + j \mathrm{arccos} \frac{5}{6} + k \mathrm{arccos} \frac{7}{8} }[/math]
W 301 1230 Cartesian product of V with itself, minus vertices at more than [math]\displaystyle{ \sqrt{3} }[/math] from the centre (i.e. [math]\displaystyle{ \mathrm{trim}(V \oplus V, \sqrt{3}) }[/math])
[math]\displaystyle{ W_1 }[/math] Trimmed product of V with itself ([math]\displaystyle{ \mathrm{trim}(V \oplus V, 1.95) }[/math])
M 1345 8268 Cartesian product of W and H ([math]\displaystyle{ W \oplus H }[/math]) [math]\displaystyle{ {\bf Z}[\omega_1, \omega_3] }[/math] All 4-colorings have a monochromatic triangle in the central copy of H
[math]\displaystyle{ M_1 }[/math] 278 Deleting vertices from M while maintaining its restriction on H All 4-colorings have a monochromatic triangle in the central copy of H
[math]\displaystyle{ M_2 }[/math] 7075 Sum of H with a trimmed product of [math]\displaystyle{ V_1 }[/math] with itself Not 4-colorable
N 20425 151311 Contains 52 copies of M arranged around the H-copies of L [math]\displaystyle{ {\bf Z}[\omega_1, \omega_3, \omega_4, \omega_{16}] }[/math] Not 4-colorable
[math]\displaystyle{ G_0 }[/math] 1585 7909 N "shrunk" by stepwise deletions and replacements of vertices Not 4-colorable
G 1581 7877 Deleting 4 vertices from [math]\displaystyle{ G_0 }[/math] Not 4-colorable
[math]\displaystyle{ G_1 }[/math] 1577 Deleting 8 vertices from [math]\displaystyle{ G_0 }[/math] Not 4-colorable
[math]\displaystyle{ G_2 }[/math] 874 4461 Juxtaposing two copies of M and shrinking [math]\displaystyle{ {\bf Z}[\omega_1, \omega_3, \omega_4] }[/math] Not 4-colorable
[math]\displaystyle{ G_3 }[/math] 826 4273 Not 4-colorable
[math]\displaystyle{ G_4 }[/math] 803 4144 Not 4-colorable
R Union of [math]\displaystyle{ W_1 }[/math] and a rotated copy of [math]\displaystyle{ W_1 }[/math]
[math]\displaystyle{ \mathrm{trim}(R \oplus H, 1.67) }[/math] 2563 Trimmed sum of R and H Not 4-colorable
[math]\displaystyle{ V \oplus V \oplus H }[/math] [math]\displaystyle{ {\bf Z}[\omega_1, \omega_3, \omega_{64/9}] }[/math] Has two vertices forced to be the same color in a 4-coloring; also no monochromatic triangles
[No name assigned 745 Subgraph of [math]\displaystyle{ V \oplus V \oplus H }[/math] Has two vertices forced to be the same color in a 4-coloring
[math]\displaystyle{ V_a \oplus V_x \oplus H \cup V_b \oplus V_y \oplus H }[/math] 3085 Not 4-colorable
[math]\displaystyle{ V_a \oplus V_z \oplus H \cup V_b \oplus V_y \oplus H }[/math] 3049 Not 4-colorable
No name assigned 1951 Trimmed version of [math]\displaystyle{ V_a \oplus V_x \oplus H \cup V_b \oplus V_y \oplus H }[/math] Not 4-colorable
[math]\displaystyle{ V_A \oplus V_A \oplus V_A }[/math] 6937 44439 [math]\displaystyle{ {\bf Z}[\omega_1, \omega_3, \omega_4] }[/math] Not 4-colorable

Lower bounds

In [P1988], Pritikin proved that every graph with at most 12 vertices is 4-colorable, and every graph with at most 6197 vertices is 6-colorable. Pritikin's bounds are obtained by coloring the plane with k colors and an additional “wild” color such that points of unit distance are both allowed to receive the wild color. If the wild color occupies a small fraction p of the plane, then an exercise in the probabilistic method gives that any fixed unit-distance graph with n vertices enjoys an embedding in the plane that avoids the wild color (and is therefore k-colorable) provided n<1/p. Pritikin’s coloring for the k=4 case cannot be improved without improving on the densest known subset of the plane that avoids unit distances (originally due to Croft in 1967). See this MO thread for additional information. As such, improving the bound in the k=4 case might require a new technique, whereas the k=5 and 6 cases might be amenable to optimization.

A "tile-based" colouring of the plane must have at least 6 colours, as shown by Townsend [Tow2005]; the same proof with a minor error was also derived by Woodall [W1973]. In [T1999], Thomassen showed that any tiling-based 6-coloring woould have to be be "unscaleable", i.e. the maximum diameter of a tile and the minimum separation of same-coloured tiles must both be exactly 1 (so that the distance 1 is excluded by suitable colouring of the boundary points).

Further questions

  • What are the independence ratios of the above unit distance graphs?
  • What are the fractional chromatic numbers of these graphs?
  • What are the Lovasz numbers of these graphs?
  • What about the Erdos unit distance graph ([math]\displaystyle{ n }[/math] vertices, [math]\displaystyle{ n^{1+c/\log\log n} }[/math] edges)?
  • Can we use de Grey’s graph to construct unit-distance graphs that are not 5-colorable? To answer this question, we first need to understand how 5-colorings of de Grey’s graph force small collections of vertices to be colored. Varga and Nazgand provide some thoughts along these lines. Even if we can’t stitch together a 6-chromatic unit-distance graph with these ideas, we might be able to apply them to prove that the measurable chromatic number of the plane is at least 6.
  • It appears as though the coordinates of our smallest 5-chromatic graph lie in [math]\displaystyle{ \mathbb{Q}[\sqrt{3}, \sqrt{5}, \sqrt{11}] }[/math] (see this). If we view the plane as the complex plane, what is the smallest ring that admits a 5-chromatic single-distance graph? Every single-distance graph in the Eistenstein integers and Gaussian integers is 2-chromatic (see this). David Speyer suggests looking at [math]\displaystyle{ \mathbb{Z}[\frac{1+\sqrt{-71}}{2}] }[/math] next.

Blog, forums, and media

Code and data

This dropbox folder will contain most of the data and images for the project.

Data:

Code:

Software:

Wikipedia

Bibliography

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Hadwiger-Nelson_problem&oldid=10569"