Difference between revisions of "Hadwiger-Nelson problem"
(→Notable unit distance graphs) |
(→Lower bounds) |
||
Line 257: | Line 257: | ||
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 [https://mathoverflow.net/questions/298198/how-much-of-the-plane-is-4-colorable 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. | 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 [https://mathoverflow.net/questions/298198/how-much-of-the-plane-is-4-colorable 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. | ||
− | In [T1999], Thomassen | + | 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 == | == Further questions == |
Revision as of 16:42, 1 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]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.
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).
Contents
Polymath threads
- Polymath proposal: finding simpler unit distance graphs of chromatic number 5, Aubrey de Grey, Apr 10 2018. (Active discussion thread)
- Polymath16, first thread: Simplifying de Grey’s graph, Dustin Mixon, Apr 14, 2018. (Inactive research thread)
- Polymath16, second thread: What does it take to be 5-chromatic?, Dustin Mixon, Apr 22, 2018. (Active research thread)
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]CNP[/math]; in particular, if one can find a unit distance graph with no 4-colorings, then [math]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]G_1 \oplus G_2[/math] denotes the Minkowski sum of two unit distance graphs [math]G_1,G_2[/math] (vertices in [math]G_1 \oplus G_2[/math] are sums of the vertices of [math]G_1,G_2[/math]). [math]G_1 \cup G_2[/math] denotes the union. [math]\mathrm{rot}(G, \theta)[/math] denotes [math]G[/math] rotated counterclockwise by [math]\theta[/math]. [math]\mathrm{trim}(G,r)[/math] denotes the trimming of [math]G[/math] after removing all vertices of distance greater than [math]r[/math] from the origin.
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.
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 |
Golomb graph | 10 | 18 | Contains the center and vertices of a hexagon and equilateral triangle | 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 |
[math]L_1[/math] | 97 | Has 40 copies of H | All 4-colorings contain an H with a monochromatic triangle | |
[math]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]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]V_1[/math] | 61 | 60 | Union of V and a rotation of V: [math]V \cup \mathrm{rot}(V, \mathrm{arccos}(7/8))[/math] | |
[math]V_a[/math] | 25 | 24 | Star graph | |
[math]V_b[/math] | 25 | 24 | Star graph | |
[math]V_x[/math] | 13 | 12 | Subgraph of [math]V_a[/math] | |
[math]V_z[/math] | Subgraph of [math]V_a[/math]; shares a line of symmetry with [math]V_a[/math] | |||
[math]V_y[/math] | 13 | 12 | Subgraph of [math]V_b[/math] | |
[math]V_A[/math] | 37 | 36 | Unit vectors with angles [math]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]\sqrt{3}[/math] from the centre (i.e. [math]\mathrm{trim}(V \oplus V, \sqrt{3})[/math]) | |
[math]W_1[/math] | Trimmed product of V with itself ([math]\mathrm{trim}(V \oplus V, 1.95)[/math]) | |||
M | 1345 | 8268 | Cartesian product of W and H ([math]W \oplus H[/math]) | All 4-colorings have a monochromatic triangle in the central copy of H |
[math]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]M_2[/math] | 7075 | Sum of H with a trimmed product of [math]V_1[/math] with itself | Not 4-colorable | |
N | 20425 | 151311 | Contains 52 copies of M arranged around the H-copies of L | Not 4-colorable |
[math]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]G_0[/math] | Not 4-colorable |
[math]G_1[/math] | 1577 | Deleting 8 vertices from [math]G_0[/math] | Not 4-colorable | |
[math]G_2[/math] | 874 | 4461 | Juxtaposing two copies of M and shrinking | Not 4-colorable |
[math]G_3[/math] | 826 | 4273 | Not 4-colorable | |
R | Union of [math]W_1[/math] and a rotated copy of [math]W_1[/math] | |||
[math]\mathrm{trim}(R \oplus H, 1.67)[/math] | 2563 | Trimmed sum of R and H | Not 4-colorable | |
[math]V \oplus V \oplus H[/math] | Has two vertices forced to be the same color in a 4-coloring | |||
[No name assigned | 745 | Subgraph of [math]V \oplus V \oplus H[/math] | Has two vertices forced to be the same color in a 4-coloring | |
[math]V_a \oplus V_x \oplus H \cup V_b \oplus V_y \oplus H[/math] | 3085 | Not 4-colorable | ||
[math]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]V_a \oplus V_x \oplus H \cup V_b \oplus V_y \oplus H[/math] | Not 4-colorable | |
[math]V_A \oplus V_A \oplus V_A[/math] | 6937 | 44439 | 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?
- The Lovasz theta function value of Lovasz number of [math]G_2[/math] at the complement is in the interval [3.3746, 3.3748].
- What about the Erdos unit distance graph ([math]n[/math] vertices, [math]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]\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]\mathbb{Z}[\frac{1+\sqrt{-71}}{2}][/math] next.
Blog, forums, and media
- More On Coloring The Plane, Richard Lipton, May 22, 2011.
- Has there been a computer search for a 5-chromatic unit distance graph?, Juno, Apr 16, 2016.
- The chromatic number of the plane is at least 5, Jordan Ellenberg, Apr 9 2018.
- Aubrey de Grey: The chromatic number of the plane is at least 5, Gil Kalai, Apr 10 2018.
- The chromatic number of the plane is at least 5, Dustin Mixon, Apr 10, 2018.
- Amazing progress on long-standing problems, Scott Aaronson, Apr 11 2018.
- The chromatic number of the plane is at least 5, Part II, Dustin Mixon, Apr 13 2018.
- A 5-chromatic unit distance graph, Ed Pegg, Apr 13 2018.
- The chromatic number of the plane is at least 5, Katie Steckles, Apr 17 2018.
- Decades-Old Graph Problem Yields to Amateur Mathematician, Evelyn Lamb, Quanta, Apr 17, 2018.
- Zahlen, bitte! 5 - Wie bunt ist die Ebene?, Harald Bögeholz, Heise, Apr 17, 2018.
- Amateur mathematician cracks decades-old math problem, Katie Langin, Science News, Apr 18, 2018.
- How much of the plane is 4-colorable?, Dustin Mixon, Apr 18, 2018.
- An Amateur Solved a 60-Year-Old Maths Problem About Colours That Can Never Touch, Peter Dockrill, ScienceAlert, Apr 19, 2018.
- Amateur mathematician Aubrey de Grey, known for his work on anti-aging, solves decades-old problem, Mihai Andrei, ZME Science, Apr 20, 2018.
- 5 nuances d’Aubrey de Grey, Automaths, Apr 21, 2018.
Code and data
This dropbox folder will contain most of the data and images for the project.
Data:
- The 1585-vertex graph in DIMACS format
- A naive translation of 4-colorability of this graph into a SAT problem in DIMACS format
- The vertices of this graph in explicit Sage notation
- The graph [math]G_2[/math]: vertices (Mathematica) edges (DIMACS)
- The graph [math]G_3[/math]: vertices (Mathematica) edges (DIMACS) Visualization
- The densest unit-distance graphs on an [math]n\times n[/math] grid for [math]n=10,20,\ldots,100[/math] (DIMACS format).
Code:
- MATLAB script for computing Lovasz number
- Python code for converting a list of vertices in Mathematica format into vertices in Z^n
- Python code for converting a DIMACS edge list into a CNF formula (forcing up to 3 suitable vertices to a fixed color, to break some symmetries)
Software:
Wikipedia
Bibliography
- [CR2015] D. Cranston, L. Rabern, The fractional chromatic number of the plane, arXiv:1501.01647
- [deBE1951] N. G. de Bruijn, P. Erdős, 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.
- [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.
- [T1999] C. Thomassen, On the Nelson unit distance coloring problem, Amer. Math. Monthly 106 (1999) 850-853.