Hadwiger-Nelson problem

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 in the plane.
  • Improve the corresponding bound in higher dimensions.
  • Improve the current record of 383/102 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 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. (Inactive research thread)
• Polymath16, third thread: Is 6-chromatic within reach?, Dustin Mixon, May 1, 2018. (Inactive research thread)
• Polymath16, fourth thread: Applying the probabilistic method, Dustin Mixon, May 5, 2018. (Inactive research thread)
• Polymath16, fifth thread: Human-verifiable proofs, Dustin Mixon, May 10, 2018. (Inactive research thread)
• Polymath16, sixth thread: Wrestling with infinite graphs, Dustin Mixon, May 29, 2018. (Inactive research thread)
• Polymath16, seventh thread: Upper bounds, Dustin Mixon, June 16, 2018. (Inactive research thread)
• Polymath16, eighth thread: More upper bounds, Dustin Mixon, June 24, 2018. (Inactive research thread)
• Polymath16, ninth thread: Searching for a 6-coloring, Dustin Mixon, July 2, 2018. (Inactive research thread)
• Polymath16, tenth thread: Open SAT instances, Dustin Mixon, Aug 28, 2018. (Inactive research thread)
• Polymath16, eleventh thread: Chromatic numbers of planar sets, Dustin Mixon, Sep 14, 2018. (Inactive research thread)
• Polymath16, twelfth thread: Year in review and future plans, Dustin Mixon, Mar 23, 2019. (Inactive research thread)
• Polymath16, thirteenth thread: Bumping the deadline?, Dustin Mixon, July 8, 2019. (Inactive research thread)
• Polymath16, fourteenth thread: Automated graph minimization?, Dustin Mixon, Aug 6, 2019. (Inactive research thread)
• Polymath16, fifteenth thread: Writing the paper and chasing down loose ends, Dustin Mixon, Dec 12, 2019. (Inactive research thread)
• Polymath16, sixteenth thread: Writing the paper and chasing down loose ends, II, Dustin Mixon, May 11, 2020. (Inactive research thread)
• Polymath16, seventeenth thread: Declaring victory, Dustin Mixon, Feb 1, 2021. (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]\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 complex numbers of unit modulus [math]\displaystyle{ \omega_t := \exp( i \arccos( 1 - \tfrac{1}{2t} )) }[/math] for various natural numbers [math]\displaystyle{ t }[/math], particularly the Loeschian numbers [math]\displaystyle{ 1,3,4,7,9,12,\dots }[/math]. These numbers arise naturally as the apex angle of a [math]\displaystyle{ \sqrt{t}, \sqrt{t}, 1 }[/math] isosceles triangle, and the distances [math]\displaystyle{ \sqrt{t} }[/math] are the distances that arise in the triangular lattice. The rings [math]\displaystyle{ R_n = {\bf Z}[ \omega_{t_1}, \dots, \omega_{t_n}] }[/math], where [math]\displaystyle{ t_1,t_2,\dots }[/math] are the Loeschian numbers, seem particularly relevant, thus [math]\displaystyle{ R_0 = {\bf Z}, R_1 = {\bf Z}[\omega_1], R_2 = {\bf Z}[\omega_1, \omega_3] }[/math], etc.. Closely related rings are the rings [math]\displaystyle{ \overline{R_n} }[/math] generated by the unit vectors in [math]\displaystyle{ R_n }[/math] and their inverses.

Note that the square root [math]\displaystyle{ \eta = \exp( i \frac{1}{2} \arccos \frac{5}{6} ) }[/math] of [math]\displaystyle{ \omega_3 }[/math] lies in [math]\displaystyle{ R_2 }[/math], thanks to the identity

[math]\displaystyle{ \eta = (\omega_1^4 + \omega_1^5) (\omega_3 - 1). }[/math]

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 [math]\displaystyle{ \sqrt{3} }[/math]-triangle. Every 5-coloring has a monochrome [math]\displaystyle{ \sqrt{3} }[/math]-edge or a monochrome [math]\displaystyle{ 2 }[/math]-edge
J	31	72	Contains 13 copies of H	[math]\displaystyle{ {\bf Z}[\omega_1] }[/math]	Has essentially six 4-colorings in which no H has a monochromatic [math]\displaystyle{ \sqrt{3} }[/math]-triangle
K	61	150	Contains 2 copies of J		In all 4-colorings lacking an H with a monochromatic [math]\displaystyle{ \sqrt{3} }[/math]-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 [math]\displaystyle{ \sqrt{3} }[/math]-triangle
[math]\displaystyle{ L_1 }[/math]	97		Has 40 copies of H		All 4-colorings contain an H with a monochromatic [math]\displaystyle{ \sqrt{3} }[/math]-triangle
[math]\displaystyle{ L_2 }[/math]	120	354			All 4-colorings contain an H with a monochromatic [math]\displaystyle{ \sqrt{3} }[/math]-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	[math]\displaystyle{ \{0\} \cup \{ \omega_1^x \omega_3^{y/2}: x=0,\dots,5; y=0,\dots,4\} }[/math]	[math]\displaystyle{ {\bf Z}[\omega_1,\omega_3] }[/math]
[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{ {\bf Z}[\omega_1,\omega_3, \omega_4] }[/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]	No 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		No 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
[math]\displaystyle{ G_5 }[/math]	633	3166	Subgraph of two copies of [math]\displaystyle{ V \oplus V \oplus V }[/math]		Not 4-colorable
[math]\displaystyle{ G_6 }[/math]	610	3000			Not 4-colorable
[math]\displaystyle{ G_7 }[/math]	553	2722			Not 4-colorable
[math]\displaystyle{ G_8 }[/math]	529	2670			Not 4-colorable
[math]\displaystyle{ G_8' }[/math]	529	2630			Not 4-colorable
[math]\displaystyle{ G_9 }[/math]	525	2605			Not 4-colorable
[math]\displaystyle{ G_{10} }[/math]	517	2579			Not 4-colorable
[math]\displaystyle{ G_{11} }[/math]	510	2508			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 [math]\displaystyle{ \sqrt{3} }[/math]-triangles
[math]\displaystyle{ G_{745} }[/math]	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
[math]\displaystyle{ G_{1951} }[/math]	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
[math]\displaystyle{ G_{40} }[/math]	40	82			Any 4-coloring that avoids a monochromatic [math]\displaystyle{ \sqrt{11/3} }[/math]-edge has two specific vertices forced to be the same color
[math]\displaystyle{ G_{79} }[/math]	79	165	Spindling of [math]\displaystyle{ G_{40} }[/math]		Any 4-coloring has a monochromatic [math]\displaystyle{ \sqrt{11/3} }[/math]-edge
[math]\displaystyle{ G_{49} }[/math]	49	180		[math]\displaystyle{ {\mathbf Q}[\sqrt{3},\sqrt{11}]^2 }[/math]	Any 4-coloring either has a specific [math]\displaystyle{ \sqrt{11/3} }[/math]-edge monochromatic, or a monochromatic [math]\displaystyle{ 1/\sqrt{3} }[/math]-triangle
[math]\displaystyle{ G_{51} }[/math]	51				Has a specific [math]\displaystyle{ 1/\sqrt{3} }[/math]-triangle which cannot be monochromatic in a 4-coloring of plane
[math]\displaystyle{ G_{627} }[/math]	627	2982	Contains [math]\displaystyle{ G_{51} }[/math]		Has a specific [math]\displaystyle{ 1/\sqrt{3} }[/math]-triangle which cannot be monochromatic in a 4-coloring
[math]\displaystyle{ G_{103} }[/math]	103				All 4-colorings contain a monochromatic [math]\displaystyle{ 2/\sqrt{3} }[/math]-edge
regular pentagon with unit side length	5	5			All 4-colorings contain a monochromatic [math]\displaystyle{ (\sqrt{5}+1)/2 }[/math]-edge
regular pentagon with [math]\displaystyle{ (\sqrt{5}-1)/2 }[/math] side length	5	5			All 4-colorings contain a monochromatic [math]\displaystyle{ (\sqrt{5}-1)/2 }[/math]-edge
[math]\displaystyle{ G_{21} }[/math]	21	49		[math]\displaystyle{ {\bf Z}[\omega_1,\omega_3] }[/math]	Implies [math]\displaystyle{ p_2 \geq 1/4 }[/math]
[math]\displaystyle{ G_{43} }[/math]	43		[math]\displaystyle{ \{0,1,\eta,\overline{\eta}, \eta -\overline{\eta}, \eta - \overline{\eta}\omega_1, 1+\eta \omega_1^2, 1+\overline{\eta\omega_1^2}\} \cdot \langle \omega_1 \rangle }[/math]	[math]\displaystyle{ {\bf Z}[\omega_1,\omega_3] }[/math]	Origin cannot be bichromatic
[math]\displaystyle{ G_{24} }[/math]	24				Origin cannot be bichromatic
[math]\displaystyle{ G_{26} }[/math]	26		Except for the origin, all vertices lie on one of 3 unit circles.		Origin cannot be bichromatic
[math]\displaystyle{ G_{34} }[/math]	34				Origin cannot be bichromatic
[math]\displaystyle{ G_{30} }[/math]	30				Origin cannot be bichromatic

Lower bounds under various criteria

Order of a k-chromatic unit-distance graph in the plane

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. Progress thus far is as follows:

Every unit distance graph with at most 16 vertices is 5-colorable.

Every unit distance graph with at most 24 vertices is 5-colorable.

Every unit distance graph with at most 6906 vertices is 6-colorable.

Tile-based colourings (tilings)

Let a tile-based colouring (hereafter a "tiling") be one consisting of monochromatic regions ("tiles"), each of finite area greater than some positive number, and each bounded by a Jordan curve. This class of colourings is of interest because, even though a 5-colouring of the plane has not been ruled out, such a colouring cannot be a tiling (as shown by Townsend [Tow2005], correcting a minor error in an earlier proof by Woodall [W1973]). An independent proof was given by Coulson [C2004]. In [T1999], Thomassen further showed that any tile-based 6-coloring would have to 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).

It is, therefore, of interest to determine whether the scaleability criterion relied upon by Thomassen can be removed, i.e. whether a (necessarily unscaleable) tiling can have only six colours.

Denote the annulus-like region consisting of all points at unit distance from some point in a tile T by AE_T, standing for "annulus of exclusion". Admissible tilings of the plane can in principle have cases where two tiles lie inside each other's AE; we know of such tilings that are 7-colourable and are not trivially transformable into tilings lacking such "Siamese tiles". Tiles in a k-colour tiling that features Siamese tiles can in principle have arbitrarily many vertices (as far as we yet know). By contrast, if a k-colour tiling does not feature Siamese tiles, much can be said: no tile can have more than k-1 vertices, and at most k of them can meet at a vertex (or a simple transformation can make this so without making the tiling non-k-colourable). There are, therefore, only finitely many ways to fit such tiles together, which makes it attractive to try to demonstrate computationally that a 6-colour tiling without Siamese tiles cannot exist, especially since we have tentative reasons to hope that tilings that do have Siamese tiles can be proven impossible by other means.

We can begin by enumerating all admissible neighbourhoods of a tile in a 6-colour tiling. Each vertex V of a tile T can have at most three other tiles meeting it, not counting the tiles that share the edges of T that meet at V; call these the vertex-neighbours of T at V. If two vertices of T have vertex-neighbours of the same colour, those vertices must be unit distance apart; similarly, if a vertex-neighbour of T at V is the same colour as an edge-neighbour of T, that edge must be an arc of radius 1 centred at V. This allows us to encode each admissible tile neighbourhood as a list d of valencies (each between 3 and 6) of the tile's n = 2, 3, 4 or 5 vertices (we can ignore the one-vertex case), together with a list S of vertex pairs {v_i,v_j} and vertex-edge pairs {v_i,e_j} that must be unit distance apart. (We index edges such that e_i joins v_i and v_i+1.) The combination {d,S} must then obey a number of other constraints:

1. Edges at unit distance from a point include their ends: thus, if {v_i,e_j} is in S, {v_i,v_j} and {v_i,v_j+1} must also be.
2. A vertex cannot be at distance 1 from itself: thus, given (1), neither {v_i,e_i} nor {v_i,e_i-1} can be in S.
3. The diameter of neighbouring tiles cannot exceed 1: thus, if d_i = 3, at least one of {v_i-1,v_i} and {v_i,v_i+1} must not be in S.
4. Quadrilaterals ABCD with AB=CD=1 must have at least one of AC,AD,BC,BD longer than 1: thus, no disjoint pair {v_i,v_i+1} and {v_j,v_k} can both be in S.
5. Six tiles meeting at a vertex must cover a unit-radius disk: thus,
   • if n=4 or 5, at most one d_i can be 6, and if n=2, neither can.
   • if d_i = 6, {v_i-1,v_i+1} must be in S.
6. Pigeonhole principle wrt any two vertices: for all i,j, if d_i + d_j + min(|j-i|,n-|j-i|,n-2) >= 10, {v_i,v_j} must be in S.
7. Pigeonhole principle wrt a vertex and the tile's edges: for all i, at least d_i + n-8 of the {v_i,e_j} must be in S.
8. Pigeonhole principle wrt all edges and vertices combined: If d = {4,4,4} or some d_i = d_i+1 = 4 then S must include a {v_i,e_j}.

We are working to enumerate all cases that satisfy this list of constraints. Once that is done, we will examine which pairs (and beyond) of admissible tiles can be juxtaposed. The hope is that all cases will run into irreconcileable conflicts at a manageable radius from an intial tile; this is based on our failure thus far to 6-tile a disk of radius greater than slightly over 2.

Colourings that are not tile-based

Intuitively, a colouring of the plane using the minimum number of colours will surely be a tiling. However, this is not necessarily so, and indeed the possibility that a non-tile-based 5-colouring of the plane exists has not been ruled out. However, no example has yet been found (to our knowledge) of a non-tile-based partitioning of the plane that cannot trivially be transformed into a tiling without increasing its chromatic number. Do such partitionings exist? If they could be proved not to, the chromatic number of the plane would be lower-bounded at 6 without the discovery of a 6-chromatic finite unit-distance graph.

An intermediate case that may be worth exploring (but we have not yet done so) is that of partitionings in which each point is part of a monochromatic region of positive area bounded by a Jordan curve, but in which arbitrarily small such regions are present. The proofs mentioned above of a lower bound of 6 rely on the existence of a positive minimum area for a tile.

Virtual edge

Warning: other definitions have been proposed and the exact definition of this notion is currently under discussion. The clamping of graph G in this section may be interpreted as the devirtualization of all bichromatic virtual edges with length [math]\displaystyle{ d }[/math] and chromatic number [math]\displaystyle{ 4 }[/math].

A virtual edge of a unit distance graph [math]\displaystyle{ G }[/math] is a distance [math]\displaystyle{ d }[/math] with the property that every 4-coloring of [math]\displaystyle{ G }[/math] contains a monochromatic pair of vertices of distance exactly [math]\displaystyle{ d }[/math]. Observe that if a unit distance graph [math]\displaystyle{ G }[/math] has a virtual edge at distance [math]\displaystyle{ d }[/math], and if there is another unit distance graph [math]\displaystyle{ H }[/math] with a pair of vertices at distance [math]\displaystyle{ d }[/math] that cannot be monochromatic in a 4-coloring, then we can create a non-4-colorable unit distance graph by "clamping" a copy of [math]\displaystyle{ H }[/math] to every virtual edge in [math]\displaystyle{ G }[/math].

Known examples of virtual edges include:

• [math]\displaystyle{ G_{40} }[/math] has a virtual edge at distance [math]\displaystyle{ \sqrt{11/3} }[/math].
• [math]\displaystyle{ V \oplus V \oplus H }[/math] has a (single) virtual edge at distance [math]\displaystyle{ 8/3 }[/math].
• [math]\displaystyle{ (\sqrt{3}\pm 1)/\sqrt{2} }[/math] are virtual edges of some graphs.

Bichromatic virtual edge

Definition

If a unit distance graph [math]\displaystyle{ H }[/math] exists with a specific pair of vertices which are distance [math]\displaystyle{ d }[/math] apart and is bichromatic in all proper [math]\displaystyle{ n }[/math]-colorings of [math]\displaystyle{ H }[/math], then we say that [math]\displaystyle{ H }[/math] virtualizes a bichromatic virtual edge with length [math]\displaystyle{ d }[/math] and chromatic number [math]\displaystyle{ n }[/math].

Vacuous properties

Considering the graph of the entire plane, all distances correspond to a virtual edge of chromatic number [math]\displaystyle{ CNP-1 }[/math].

If a bichromatic virtual edge with length [math]\displaystyle{ d }[/math] and chromatic number [math]\displaystyle{ n }[/math] exists, then a bichromatic virtual edge with length [math]\displaystyle{ d }[/math] and chromatic number [math]\displaystyle{ n-1 }[/math] exists.

Convenience and devirtualization

Bichromatic virtual edges behave the same as the unit edge(which is a bichromatic virtual edge of every chromatic number), and thus may be used to simplify the construction of graphs.

Recursively replacing bichromatic virtual edges of a graph [math]\displaystyle{ G }[/math] with graphs which virtualize the bichromatic virtual edges through clamping produces a unit distance graph [math]\displaystyle{ G' }[/math] where [math]\displaystyle{ \chi(G')\geq\chi(G) }[/math].

Devirtualizing bichromatic virtual edges of a graph [math]\displaystyle{ G }[/math] (i.e. clamping) has no benefit unless nontrivial points of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ H_0 }[/math] overlap or nontrivial points of [math]\displaystyle{ H_1 }[/math] and [math]\displaystyle{ H_0 }[/math] overlap, where [math]\displaystyle{ H_0 }[/math] and [math]\displaystyle{ H_1 }[/math] are graphs virtualizing bichromatic virtual edges of [math]\displaystyle{ G }[/math]. Such overlaps may cause [math]\displaystyle{ \chi(G')\gt \chi(G) }[/math]. If no nontrivial overlaps exist, then [math]\displaystyle{ \chi(G')=\max\left(\chi(G),\chi(H_0),\chi(H_1),\dots\right) }[/math].

Because more than 1 graph virtualizes any given bichromatic virtual edge for a fixed length and fixed chromatic number, multiple devirtualizations exist for every finite graph.

Relation to rings

A devirtualized ring of graph [math]\displaystyle{ G }[/math] is a ring which contains all the vertices of a devirtualization of [math]\displaystyle{ G }[/math], where the vertices are interpreted as complex numbers.

Use the implied shorthand for arbitrary sets [math]\displaystyle{ \mathbb{S}[\left\{a,b,c,\dots\right\}]=\mathbb{S}[a,b,c,\dots] }[/math].

Let the vertices of graph [math]\displaystyle{ G }[/math] generate the ring [math]\displaystyle{ S_0[T_0] }[/math]. Let the bichromatic virtual edges be virtualizable by the graphs [math]\displaystyle{ H_1,\dots,H_m }[/math]. Let [math]\displaystyle{ S_k[T_k] }[/math] be the ring generated by the vertices of [math]\displaystyle{ H_k }[/math]. Let [math]\displaystyle{ S }[/math] be the ring generated by [math]\displaystyle{ \bigcup_{k=0}^m S_k }[/math]. Let [math]\displaystyle{ T=\bigcup_{k=0}^m T_k }[/math]. Then [math]\displaystyle{ S[T] }[/math] is a devirtualized ring of [math]\displaystyle{ G }[/math].

As multiple graphs may virtualize the same virtual edge, careful choice may be required to minimize the set [math]\displaystyle{ T }[/math].

Multiplicative property

Let [math]\displaystyle{ H_0 }[/math] be a graph virtualizing a bichromatic virtual edge with length [math]\displaystyle{ d_0 }[/math] and chromatic number [math]\displaystyle{ n }[/math]. Let [math]\displaystyle{ H_1 }[/math] be a graph virtualizing a bichromatic virtual edge with length [math]\displaystyle{ d_1 }[/math] and chromatic number [math]\displaystyle{ n }[/math]. Create a graph [math]\displaystyle{ H_2 }[/math] by scaling [math]\displaystyle{ H_0 }[/math] by a factor of [math]\displaystyle{ d_1 }[/math]. Graph [math]\displaystyle{ H_2 }[/math] then virtualizes a bichromatic virtual edge length [math]\displaystyle{ d_0d_1 }[/math] and chromatic number [math]\displaystyle{ n }[/math].

Notable bichromatic virtual edges

Chromatic number	Length [math]\displaystyle{ d }[/math]	Proof
any	1	trivial case
2	[math]\displaystyle{ 0\leq d\leq 3 }[/math]	moving the flexible parts of the graph (0,0),(0,1),(0,2),(0,3)
3	[math]\displaystyle{ \left\{\left|\frac{(3+\sqrt{-3})k}{2}+\sqrt{-3}j+(-1)^r\right| \mid k,j\in\mathbb{Z}, r\in\mathbb{R}\right\} }[/math]	equilateral triangle tiling

Continuous ranges of bichromatic virtual edges

Flexible graphs might produce continuous ranges of lengths of bichromatic virtual edges of chromatic number [math]\displaystyle{ n }[/math] without having a specific pair which is monochrome for every [math]\displaystyle{ n }[/math]-coloring. Let the range of lengths be on the interval [math]\displaystyle{ d_0\leq d\leq d_1 }[/math].

If [math]\displaystyle{ 1 \lt d_1 }[/math], then let [math]\displaystyle{ k\in\mathbb{Z}^+,d_0^{k+1} \leq d_1^k }[/math]. The multiplicative property of bichromatic virtual edges implies the existence of bichromatic virtual edges of chromatic number [math]\displaystyle{ n }[/math] for all lengths larger than [math]\displaystyle{ d_0^k }[/math]. A finite area allowed to be the same color, the infinite area of the plane, and a finite upper bound on CNP implies [math]\displaystyle{ CNP\gt n }[/math].

If [math]\displaystyle{ d_0 \lt 1 }[/math], then let [math]\displaystyle{ k\in\mathbb{Z}^+,d_1^{k+1} \geq d_0^k }[/math]. The multiplicative property of bichromatic virtual edges implies the existence of bichromatic virtual edges of chromatic number [math]\displaystyle{ n }[/math] for all non-zero lengths smaller than [math]\displaystyle{ d_1^k }[/math]. Considering a set of [math]\displaystyle{ CNP+1 }[/math] points all within distance [math]\displaystyle{ d_1^k }[/math] of each other implies [math]\displaystyle{ CNP\gt n }[/math].

Using a flexible bichromatic virtual edge of chromatic number [math]\displaystyle{ n }[/math] and a graph [math]\displaystyle{ H }[/math] of chromatic number [math]\displaystyle{ n+1 }[/math], a flexible a graph [math]\displaystyle{ H' }[/math] of chromatic number [math]\displaystyle{ n+1 }[/math] can be created by scaling [math]\displaystyle{ H }[/math] to some arbitrarily large or arbitrarily small size and clamping flexible bichromatic virtual edges of chromatic number [math]\displaystyle{ n }[/math] as a replacement of each rigid bichromatic virtual edge of [math]\displaystyle{ H }[/math].

[math]\displaystyle{ H }[/math] virtualizing a bichromatic virtual edge of chromatic number [math]\displaystyle{ n+1 }[/math] does not necessarily mean the graph [math]\displaystyle{ H' }[/math] virtualizes a bichromatic virtual edge.

Best known results for the chromatic number in higher dimensions

The CN in [math]\displaystyle{ \mathbb{R}^n }[/math] has been shown to be between [math]\displaystyle{ (1.239...+o(1))^n }[/math] and [math]\displaystyle{ (3+o(1))^n }[/math], and a graph construction is known that has [math]\displaystyle{ 8{n \choose 3} }[/math] vertices and an independence number of [math]\displaystyle{ \max(6n-28,4n-\max(2,n\mod 4)) }[/math], which is equivalent to a CN lower bound of [math]\displaystyle{ 2n^2(1+o(1))/9 }[/math]. For specific dimensions, the best known bounds are as follows:

Space	Lower bound on CN	Number of vertices	Number of edges	Upper bound on CN
[math]\displaystyle{ \mathbb{R}^1 }[/math]	2	2	1	2
[math]\displaystyle{ \mathbb{R}^2 }[/math]	5	510	2508	7
[math]\displaystyle{ \mathbb{R}^3 }[/math]	6	59	183	15
[math]\displaystyle{ \mathbb{R}^4 }[/math]	9	65	588	54
[math]\displaystyle{ \mathbb{R}^5 }[/math]	9			156
[math]\displaystyle{ \mathbb{R}^6 }[/math]	12	175		462
[math]\displaystyle{ \mathbb{R}^7 }[/math]	16	168	4396
[math]\displaystyle{ \mathbb{R}^8 }[/math]	19	289
[math]\displaystyle{ \mathbb{R}^9 }[/math]	22	672
[math]\displaystyle{ \mathbb{R}^{10} }[/math]	30	960
[math]\displaystyle{ \mathbb{R}^{11} }[/math]	35	1320
[math]\displaystyle{ \mathbb{R}^{12} }[/math]	37	1760

Best known results for the chromatic number of spheres

Here we list known results about spheres in 3-space, i.e., 2-dimensional spheres. Note that the distances given are the 3-dimensional Euclidean distance, not the length of the arc on the sphere surface. Most bounds are due to G.J. Simmons. For a nice summary, see [Malen |https://arxiv.org/pdf/1412.2091.pdf]. For a UD graph on the sphere with many edges, the best construction is [math]\displaystyle{ n\sqrt{\log n} }[/math] [Swanepoel-Valtr|http://personal.lse.ac.uk/swanepoe/swanepoel-valtr-unitdistance.pdf].

Radius	Lower bound on CN	comments	Upper bound on CN	comments
[math]\displaystyle{ r\lt 1/2 }[/math]	1	no unit distances	1	monochromatic sphere
[math]\displaystyle{ r=1/2 }[/math]	2	antipodes	2	monochromatic hemispheres
[math]\displaystyle{ 1/2 \lt r \le \frac{\sqrt{23-\sqrt{17}}}{8}=0.543.. }[/math]	3	odd cycle	4	tiling given by facets of tetrahedron
[math]\displaystyle{ \frac{\sqrt{23-\sqrt{17}}}{8} \lt r \le \frac{\sqrt{3-\sqrt 3}}{2}=0.563.. }[/math]	3 (4 if measurable)	odd cycle; probabilistic argument	4	tiling given by facets of tetrahedron
[math]\displaystyle{ \frac{\sqrt{3-\sqrt 3}}{2} \lt r \lt 1/\sqrt 3 }[/math]	3 (4 if measurable)	odd cycle; probabilistic argument	5	tiling given by facets of square pyramid
[math]\displaystyle{ r=1/\sqrt 3=0.577.. }[/math]	4		5	tiling given by facets of square pyramid
[math]\displaystyle{ r=1/\sqrt 2=0.707.. }[/math]	4		4	tiling given by facets of octahedron
[math]\displaystyle{ 1/\sqrt 3 \lt r \le \sqrt 3/2=0.866.. }[/math]	4	generalised Moser spindle (needs >2 diamonds for small r)	6	tiling given by facets of dodecahedron
[math]\displaystyle{ \sqrt 3/2 \lt r }[/math]	4	Moser spindle	unknown	8 should be easy, but we want 7

Best bounds for regions of the plane that can be k-colored

Four questions of this type have been studied: what proportion of the plane can be tiled with k colours, what is the widest (resp. narrowest) infinite strip that can (resp. cannot) be k-coloured, what is the largest (resp. smallest) circular disc that can (resp. cannot) be k-coloured, and what is the smallest convex shape that cannot be k-coloured (obviously an arbitrarily long but thin rectangle can be 3-coloured).

The results for the proportion of the plane for k=1,2,3,4 are due to Croft; the exact value is k[math]\displaystyle{ \sqrt{3}\tan(\theta/2) }[/math] where [math]\displaystyle{ \theta+\sin(\theta)=\pi/6 }[/math]. The other non-trivial results can be found in the polymath blog. The k=3 lower bound for the strip is here https://dustingmixon.wordpress.com/2018/08/28/polymath16-tenth-thread-open-sat-instances/#comment-5501. For k=4, see https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24282 and https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24332 and https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24375.

Shape	k=1	k=2	k=3	k=4	k=5	k=6
proportion of the plane	[math]\displaystyle{ \approx 0.229365\le }[/math]	[math]\displaystyle{ \approx 0.458729\le }[/math]	[math]\displaystyle{ \approx 0.688094\le }[/math]	[math]\displaystyle{ \approx 0.917459\le }[/math]	[math]\displaystyle{ \approx 0.959747\le }[/math]	[math]\displaystyle{ \approx 0.999855\le }[/math]
infinite strip, width	0	0	[math]\displaystyle{ \sqrt{3}/2\approx 0.866 }[/math]	[math]\displaystyle{ \approx 0.95876\le,\le 1.4 }[/math]	[math]\displaystyle{ 9/\sqrt{28}\approx 1.701\le }[/math]	[math]\displaystyle{ \sqrt{3}+\sqrt{15}/2\approx 3.669\le }[/math]
disk, diameter	1	1	[math]\displaystyle{ 2/\sqrt{3}\approx 1.155\le,\le 1.25 }[/math]	[math]\displaystyle{ \sqrt{(2-1/\sqrt{3})^2 + 1}\approx 1.739\le }[/math]	[math]\displaystyle{ \approx 2.316\le }[/math]	[math]\displaystyle{ (1+\sqrt{5})\sqrt{\frac{15+\sqrt{5}}{10}} \approx 4.2485\le }[/math]
convex shape, area	0	0	[math]\displaystyle{ \pi/2 \approx 1.5708 }[/math] (semicircle)

Constructions for disks can be found here: https://drive.google.com/file/d/1-LEV4uzd2FjGBvC6cPUL0EDY2cjQy1FB/view https://dustingmixon.wordpress.com/2018/06/16/polymath16-seventh-thread-upper-bounds/#comment-4851 https://dustingmixon.wordpress.com/2018/09/14/polymath16-eleventh-thread-chromatic-numbers-of-planar-sets/#comment-5989 https://dustingmixon.wordpress.com/2019/12/12/polymath16-fifteenth-thread-writing-the-paper-and-chasing-down-loose-ends/#comment-24836 upper bound here: https://dustingmixon.wordpress.com/2019/08/05/polymath16-fourteenth-thread-automated-graph-minimization/#comment-24369

Probabilistic formulation

See Probabilistic formulation of Hadwiger-Nelson problem.

Algebraic formulation

See Algebraic formulation of Hadwiger-Nelson problem.

Excluding bichromatic vertices

See Excluding bichromatic vertices.

Coloring [math]\displaystyle{ R_2 }[/math]

See Coloring R_2.

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]\displaystyle{ G_2 }[/math] at the complement is in the interval [3.3746, 3.3748].
• 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.
• What is the smallest cardinality of a subset of the plane which contains at least [math]\displaystyle{ n }[/math] colours in every colouring of the plane?
• Can the lower bound for [math]\displaystyle{ CNP\geq 5 }[/math] be extended to all [math]\displaystyle{ L^p }[/math] norms where [math]\displaystyle{ p\gt 1 }[/math], similar to how the Moser spindle was generalized?

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.
• Amateur Solves Part of Decades-Old Math Problem, HowStuffWorks, Apr 30, 2018.
• Het platte vlak heeft minstens vijf kleuren nodig, Kennislink, May 3, 2018.
• Egy biológus oldott meg egy olyan problémát, amire a matematikusok már 60 éve képtelenek, Index.hu, May 4, 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]\displaystyle{ G_2 }[/math]: vertices (Mathematica) edges (DIMACS)
• The graph [math]\displaystyle{ G_3 }[/math]: vertices (Mathematica) edges (DIMACS) Visualization
• The densest unit-distance graphs on an [math]\displaystyle{ n\times n }[/math] grid for [math]\displaystyle{ 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:

• CVX
• Glucose 4.0
• Minisat

Wikipedia

• Chromatic number
• de Bruijn-Erdos theorem
• Hadwiger-Nelson problem
• Lovasz number
• Moser spindle

Bibliography

• [B2008] B. Bukh, Measurable sets with excluded distances, Geometric and Functional Analysis 18 (2008), 668-697.
• [C2004] D. Coulson, On the chromatic number of plane tilings, J. Aust. Math. Soc. 77 (2004), 191–196.
• [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
• [EI2018] G. Exoo, D. Ismailescu, The chromatic number of the plane is at least 5 - a new proof, arXiv:1805.00157
• [EI2018b] G. Exoo, D. Ismailescu, The Hadwiger-Nelson problem with two forbidden distances, arXiv:1805.06055
• [F1981] K.J. Falconer, The Realization of distances in measurable subsets covering Rn, J. Combin. Theory Ser. A 31 (1981) 184–189.
• [H1945] H. Hadwiger, Uberdeckung des euklidischen Raum durch kongruente Mengen, Portugaliae Math. 4 (1945), 238–242.
• [H2018] M. Heule, Computing Small Unit-Distance Graphs with Chromatic Number 5, arXiv:1805.12181
• [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.
• [S2009] M. Shinohara, Classification of three-distance sets in two dimensional Euclidean space, European Journal of Combinatorics Volume 25, Issue 7, October 2004, Pages 1039-1058.
• [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.
• [Tow2005] Townsend, S.P., Colouring the plane with no monochrome unit. Geombinatorics XIV(4) (2005), 181-193.
• [W1973] Woodall, D.R., Distances realized by sets covering the plane. J. Combin. Theory Ser. A, 14 (1973), 187-200.