Hadwiger-Nelson problem: Difference between revisions
From Polymath Wiki
Jump to navigationJump to search
| Line 7: | Line 7: | ||
!Name!!Number of vertices!! Number of edges !! Structure !! Colorings | !Name!!Number of vertices!! Number of edges !! Structure !! Colorings | ||
|- | |- | ||
| Moser spindle | | [https://en.wikipedia.org/wiki/Moser_spindle Moser spindle] | ||
| 7 | | 7 | ||
| 11 | | 11 | ||
| Line 13: | Line 13: | ||
| Not 3-colorable | | Not 3-colorable | ||
|- | |- | ||
| H | | [https://arxiv.org/abs/1804.02385 H] | ||
| 7 | | 7 | ||
| 12 | | 12 | ||
| Line 19: | Line 19: | ||
| Has essentially four 4-colorings, two of which contain a monochromatic triangle | | Has essentially four 4-colorings, two of which contain a monochromatic triangle | ||
|- | |- | ||
| J | | [https://arxiv.org/abs/1804.02385 J] | ||
| 31 | | 31 | ||
| | | | ||
| Line 25: | Line 25: | ||
| 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 | ||
|- | |- | ||
| K | | [https://arxiv.org/abs/1804.02385 K] | ||
| 61 | | 61 | ||
| | | | ||
| Line 31: | Line 31: | ||
| In all 4-colorings without an H with a monochromatic triangle, all linking edges are monochromatic | | In all 4-colorings without an H with a monochromatic triangle, all linking edges are monochromatic | ||
|- | |- | ||
| L | | [https://arxiv.org/abs/1804.02385 L] | ||
| 121 | | 121 | ||
| | | | ||
| Line 37: | Line 37: | ||
| all 4-colorings contain an H with a monochromatic triangle | | all 4-colorings contain an H with a monochromatic triangle | ||
|- | |- | ||
| T | | [https://arxiv.org/abs/1804.02385 T] | ||
| 9 | | 9 | ||
| 15 | | 15 | ||
| Line 43: | Line 43: | ||
| | | | ||
|- | |- | ||
| U | | [https://arxiv.org/abs/1804.02385 U] | ||
| 15 | | 15 | ||
| | | | ||
| Line 49: | Line 49: | ||
| | | | ||
|- | |- | ||
| V | | [https://arxiv.org/abs/1804.02385 V] | ||
| 30 | | 30 | ||
| | | | ||
| Line 55: | Line 55: | ||
| | | | ||
|- | |- | ||
| W | | [https://arxiv.org/abs/1804.02385 W] | ||
| 301 | | 301 | ||
| | | | ||
| Line 61: | Line 61: | ||
| | | | ||
|- | |- | ||
| M | | [https://arxiv.org/abs/1804.02385 M] | ||
| 1345 | | 1345 | ||
| | | | ||
| Line 67: | Line 67: | ||
| All 4-colorings have a monochromatic triangle in H | | All 4-colorings have a monochromatic triangle in H | ||
|- | |- | ||
| N | | [https://arxiv.org/abs/1804.02385 N] | ||
| 20425 | | 20425 | ||
| | | | ||
Revision as of 08:30, 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]\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.
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 | 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 | 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 | Contains 52 copies of M arranged around the H-copies of L | Not 4-colorable |
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.
- Polymath proposal: finding simpler unit distance graphs of chromatic number 5, Aubrey de Grey, 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.
- https://dustingmixon.wordpress.com/2018/04/13/the-chromatic-number-of-the-plane-is-at-least-5-part-ii/, Dustin Mixon, Apr 13 2018.
Code and 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
Wikipedia
Bibliography
- [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.
