Difference between revisions of "Hadwiger-Nelson problem"

From Polymath1Wiki
Jump to: navigation, search
(Code and data)
(Code and data)
(4 intermediate revisions by the same user not shown)
Line 137: Line 137:
 
| 4461
 
| 4461
 
| Juxtaposing two copies of M and shrinking
 
| Juxtaposing two copies of M and shrinking
 +
| Not 4-colorable
 +
|-
 +
| [https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simplifying-de-greys-graph/#comment-3867 <math>G_3</math>]
 +
| 826
 +
| 4273
 +
|
 
| Not 4-colorable
 
| Not 4-colorable
 
|}
 
|}
Line 145: Line 151:
 
* What are the [https://en.wikipedia.org/wiki/Fractional_coloring fractional chromatic numbers] of these 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 are the [https://en.wikipedia.org/wiki/Lov%C3%A1sz_number Lovasz numbers] of these graphs?
 +
** The  Lovasz theta function value of Lovasz number of <math>G_2</math> at the complement [https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simplifying-de-greys-graph/#comment-3844 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)?
 
* What about the Erdos unit distance graph (<math>n</math> vertices, <math>n^{1+c/\log\log n}</math> edges)?
  
Line 166: Line 173:
 
* [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)]
 
* 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)]
 +
* The graph <math>G_3</math>: [http://www.cs.utexas.edu/~marijn/CNP/826.vtx vertices (Mathematica)] [http://www.cs.utexas.edu/~marijn/CNP/826.edge edges (DIMACS)] [http://www.cs.utexas.edu/~marijn/CNP/826.pdf Visualization]
 
* The [https://www.dropbox.com/sh/ufknm1v9gtbhad3/AADfw9WO1ol2ayQNJEtGf8oBa/Graphs?dl=0 densest unit-distance graphs] on an <math>n\times n</math> grid for <math>n=10,20,\ldots,100</math> (DIMACS format).
 
* The [https://www.dropbox.com/sh/ufknm1v9gtbhad3/AADfw9WO1ol2ayQNJEtGf8oBa/Graphs?dl=0 densest unit-distance graphs] on an <math>n\times n</math> grid for <math>n=10,20,\ldots,100</math> (DIMACS format).
  
Line 196: Line 204:
 
* [P1998] D. Pritikin, All unit-distance graphs of order 6197 are 6-colorable, Journal of Combinatorial Theory, Series B 73.2 (1998): 159-163.
 
* [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.
 
* [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.

Revision as of 08:23, 17 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).


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]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
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
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 Deleting vertices from M while maintaining its restriction on 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
[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

Further questions

Blog posts and other online forums

Code and data

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

Some specific files:

Code:

Software:

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.
  • [T1999] C. Thomassen, On the Nelson unit distance coloring problem, Amer. Math. Monthly 106 (1999) 850-853.