Difference between revisions of "Hadwiger-Nelson problem"
(→Notable unit distance graphs) |
|||
(16 intermediate revisions by the same user not shown) | |||
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>. This is achieved by explicitly locating finite unit distance graphs with chromatic number at least 5. | 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. | + | 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 == | == Polymath threads == | ||
Line 9: | Line 18: | ||
== Notable unit distance graphs == | == 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>. | ||
{| border=1 | {| border=1 | ||
Line 42: | Line 53: | ||
| 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 | ||
+ | |- | ||
+ | | [https://dustingmixon.wordpress.com/2018/04/13/the-chromatic-number-of-the-plane-is-at-least-5-part-ii/ <math>L_1</math>] | ||
+ | | 97 | ||
+ | | | ||
+ | | Has 40 copies of H | ||
+ | | All 4-colorings contain an H with a monochromatic triangle | ||
+ | |- | ||
+ | | [https://polymathprojects.org/2018/04/10/polymath-proposal-finding-simpler-unit-distance-graphs-of-chromatic-number-5/#comment-120295 <math>L_2</math>] | ||
+ | | 120 | ||
+ | | 254 | ||
+ | | | ||
| All 4-colorings contain an H with a monochromatic triangle | | All 4-colorings contain an H with a monochromatic triangle | ||
|- | |- | ||
Line 47: | Line 70: | ||
| 9 | | 9 | ||
| 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] | ||
Line 54: | Line 77: | ||
| 33 | | 33 | ||
| Three copies of T at 120-degree rotations | | Three copies of T at 120-degree rotations | ||
− | | | + | | |
|- | |- | ||
| [https://arxiv.org/abs/1804.02385 V] | | [https://arxiv.org/abs/1804.02385 V] | ||
Line 73: | Line 96: | ||
| Cartesian product of W and H | | Cartesian product of W and 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 | ||
− | | | + | |- |
+ | | [https://polymathprojects.org/2018/04/10/polymath-proposal-finding-simpler-unit-distance-graphs-of-chromatic-number-5/#comment-120274 <math>M_1</math>] | ||
+ | | 278 | ||
+ | | | ||
+ | | | ||
+ | | | ||
|- | |- | ||
| [https://arxiv.org/abs/1804.02385 N] | | [https://arxiv.org/abs/1804.02385 N] | ||
Line 80: | Line 108: | ||
| Contains 52 copies of M arranged around the H-copies of L | | Contains 52 copies of M arranged around the H-copies of L | ||
| Not 4-colorable | | Not 4-colorable | ||
+ | |- | ||
+ | | <math>G_0</math> | ||
+ | | 1585 | ||
| | | | ||
+ | | N "shrunk" by stepwise deletions and replacements of vertices | ||
+ | | Not 4-colorable | ||
|- | |- | ||
| [https://arxiv.org/abs/1804.02385 G] | | [https://arxiv.org/abs/1804.02385 G] | ||
| 1581 | | 1581 | ||
| 7877 | | 7877 | ||
− | | | + | | Deleting 4 vertices from <math>G_0</math> |
+ | | Not 4-colorable | ||
+ | |- | ||
+ | | [https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/ <math>G_1</math>] | ||
+ | | 1577 | ||
+ | | | ||
+ | | Deleting 8 vertices from <math>G_0</math> | ||
+ | | Not 4-colorable | ||
+ | |- | ||
+ | | [https://polymathprojects.org/2018/04/10/polymath-proposal-finding-simpler-unit-distance-graphs-of-chromatic-number-5/#comment-120318 <math>G_2</math>] | ||
+ | | 874 | ||
+ | | 4461 | ||
+ | | | ||
| Not 4-colorable | | Not 4-colorable | ||
|} | |} | ||
+ | |||
+ | == Further questions == | ||
+ | |||
+ | * What are the [http://mathworld.wolfram.com/IndependenceRatio.html independence ratios] of the above unit distance graphs? | ||
+ | * What are the [https://en.wikipedia.org/wiki/Fractional_coloring fractional chromatic numbers] of these graphs? | ||
+ | * What are the [https://en.wikipedia.org/wiki/Lov%C3%A1sz_number Lovasz numbers] of these graphs? | ||
+ | * What about the Erdos unit distance graph (<math>n</math> vertices, <math>n^{1+c/\log\log n}</math> edges)? | ||
== Blog posts and other online forums == | == Blog posts and other online forums == | ||
Line 96: | Line 148: | ||
* [https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/ The chromatic number of the plane is at least 5], Dustin Mixon, Apr 10, 2018. | * [https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/ The chromatic number of the plane is at least 5], Dustin Mixon, Apr 10, 2018. | ||
* [https://www.scottaaronson.com/blog/?p=3697 Amazing progress on long-standing problems], Scott Aaronson, Apr 11 2018. | * [https://www.scottaaronson.com/blog/?p=3697 Amazing progress on long-standing problems], Scott Aaronson, Apr 11 2018. | ||
− | * [https://dustingmixon.wordpress.com/2018/04/13/the-chromatic-number-of-the-plane-is-at-least-5-part-ii/ | + | * [https://dustingmixon.wordpress.com/2018/04/13/the-chromatic-number-of-the-plane-is-at-least-5-part-ii/ The chromatic number of the plane is at least 5, Part II], Dustin Mixon, Apr 13 2018. |
== Code and data == | == Code and data == | ||
+ | |||
+ | [https://www.dropbox.com/sh/ufknm1v9gtbhad3/AACB2xwaXYx5EGda38_L-0foa?dl=0 This dropbox folder] will contain most of the data and images for the project. | ||
+ | |||
+ | Some specific files: | ||
* [https://www.dropbox.com/s/x6kvu7b3wvdvqsn/graph.dimacs?dl=0 The 1585-vertex graph in DIMACS format] | * [https://www.dropbox.com/s/x6kvu7b3wvdvqsn/graph.dimacs?dl=0 The 1585-vertex graph in DIMACS format] | ||
* [https://www.dropbox.com/s/qk3gbpjvvsjfsc3/sat.dimacs?dl=0 A naive translation of 4-colorability of this graph into a SAT problem in DIMACS format] | * [https://www.dropbox.com/s/qk3gbpjvvsjfsc3/sat.dimacs?dl=0 A naive translation of 4-colorability of this graph into a SAT problem in DIMACS format] | ||
* [https://www.dropbox.com/s/nipqikfzcfn9o5a/vertices.sage?dl=0 The vertices of this graph in explicit Sage notation] | * [https://www.dropbox.com/s/nipqikfzcfn9o5a/vertices.sage?dl=0 The vertices of this graph in explicit Sage notation] | ||
+ | * The graph <math>G_2</math>: [http://www.cs.utexas.edu/~marijn/CNP/874.vtx vertices (Mathematica)] [http://www.cs.utexas.edu/~marijn/CNP/874.edge edges (DIMACS)] | ||
== Wikipedia == | == Wikipedia == | ||
+ | * [https://en.wikipedia.org/wiki/Graph_coloring#Chromatic_number Chromatic number] | ||
* [https://en.wikipedia.org/wiki/De_Bruijn%E2%80%93Erd%C5%91s_theorem_(graph_theory) de Bruijn-Erdos theorem] | * [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] | ||
Line 113: | Line 171: | ||
== Bibliography == | == Bibliography == | ||
+ | * [CR2015] D. Cranston, L. Rabern, [https://arxiv.org/abs/1501.01647 The fractional chromatic number of the plane], arXiv:1501.01647 | ||
* [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. | * [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. | ||
Revision as of 11:55, 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.
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. (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].
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 |
[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 | 254 | 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 | |
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 more than [math]\sqrt{3}[/math] 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 |
[math]M_1[/math] | 278 | |||
N | 20425 | 151311 | Contains 52 copies of M arranged around the H-copies of L | Not 4-colorable |
[math]G_0[/math] | 1585 | 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 | Not 4-colorable |
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]n[/math] vertices, [math]n^{1+c/\log\log n}[/math] edges)?
Blog posts and other online forums
- 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.
Code and data
This dropbox folder will contain most of the data and images for the project.
Some specific files:
- 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)
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.