View source for Probabilistic formulation of Hadwiger-Nelson problem

''This is a part of Polymath16 - for the main page, see [http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem].''

Suppose for sake of contradiction that we have a 4-coloring <math>c: {\bf C} \to \{1,2,3,4\}</math> of the complex plane with no unit edges monochromatic, thus

:<math>c(z) \neq c(w) \hbox{ whenever } |z-w| = 1. \quad (1)</math>

We can create further such colorings by composing <math>c</math> on the left with a permutation <math>\sigma \in S_4</math> on the left, and with the (inverse of) a Euclidean isometry <math>T \in E(2)</math> on the right, thus creating a new coloring <math>\sigma \circ c \circ T^{-1}: {\bf C} \to \{1,2,3,4\}</math> of the complex plane with the same property.  This is an action of the solvable group <math>S_4 \times E(2)</math>.

It is a fact that all solvable groups (viewed as discrete groups) are [https://en.wikipedia.org/wiki/Amenable_group amenable], so in particular <math>S_4 \times E(2)</math> is amenable.  This means that there is a finitely additive probability measure <math>\mu</math> on <math>S_4 \times E(2)</math> (with all subsets of this group measurable), which is left-invariant:  <math>\mu(gE) = \mu(E)</math> for all <math>g \in S_4 \times E(2)</math> and <math>E \subset S_4 \times E(2)</math>.  This gives <math>S_4 \times E(2)</math> the structure of a finitely additive probability space.  We can then define a random coloring <math>{\mathbf c}: {\bf C} \to \{1,2,3,4\}</math> by defining <math>{\mathbf c} := {\mathbf \sigma} \circ c \circ {\mathbf T}^{-1}</math>, where <math>({\mathbf \sigma},{\mathbf T})</math> is the element of the sample space <math>S_4 \times E(2)</math>.  Thus for any complex number <math>z</math>, the random color <math>{\mathbf c}(z)</math> is a random variable taking values in <math>\{1,2,3,4\}</math>.  The left-invariance of the measure implies that for any <math>(\sigma,T) \in S_4 \times E(2)</math>, the coloring <math> \sigma \circ {\mathbf c} \circ T^{-1}</math> has the same law as <math>{\mathbf c}</math>.  This gives the color permutation invariance

:<math> {\bf P}( {\mathbf c}(z_1) = c_1, \dots, {\mathbf c}(z_k) = c_k ) = {\bf P}( {\mathbf c}(z_1) = \sigma(c_1), \dots, {\mathbf c}(z_k) = \sigma(c_k) )\quad (2)</math>

for any <math>z_1,\dots,z_k \in {\bf C}</math>, <math>c_1,\dots,c_k \in \{1,2,3,4\}</math>, and <math>\sigma \in S_4</math>, and the Euclidean isometry invariance
:<math> {\bf P}( {\mathbf c}(z_1) = c_1, \dots, {\mathbf c}(z_k) = c_k ) = {\bf P}( {\mathbf c}(T(z_1)) = c_1, \dots, {\mathbf c}(T(z_k)) = c_k. \quad (3)</math>

== Bounds on <math>{\bf P}( \mathbf{c}(0) = \mathbf{c}(d) )</math> for 4-colourings ==

A class of correlations that is of particular interest is that of vertex pairs at some distance <math>d</math>.

{| border=1
|-
! distance !! Lower bound !! Lower-bounding graph !! Upper bound !! Upper-bounding graph !! Notes
|-
| >=1/2
| 
| 
| 1/2
| Spindle
| 
|-
| >=1/4
| 
| 
| 3/4
| Spindle plus triangle
| 
|-
| <math>\frac{1}{\sqrt{3}}</math>
| 1/28
| Unit diamond plus centres of triangles, together with H
| 1/3
| Unit triangle plus its centre
| 
|-
| 2
| 1/6
| H
| 
|
| 
|-
| <math>{\sqrt{3}}</math>
| 1/4
| H
| 
|
| Consider the opposite ends of a double triangle and permutations of colours to obtain the exact value 1/2
|-
| <math>{\frac{\sqrt{5}-1}{2}}</math>
| 1/5
| regular pentagon with unit side length
| 
|
| 
|-
| <math>{\sqrt{11/3}}</math>
| 1/118
| <math>G_{40}</math>
|
|
| computer-verified
|-
| 8/3
| 1
| <math>V \oplus V \oplus H</math>
| 
|
| computer-verified

|}

== Proofs of bounds ==

One can compute some correlations of the coloring exactly:

'''Lemma 1'''  Let <math>z,w \in {\bf C}</math> with <math>|z-w|=1</math>.  Then
:<math> {\bf P}( \mathbf{c}(z) = c ) = \frac{1}{4}\quad (4)</math>
for all <math>c=1,\dots,4</math>,
:<math> {\bf P}( \mathbf{c}(z) = \mathbf{c}(w) ) = 0\quad (5),</math>
and
:<math> {\bf P}( \mathbf{c}(z) = c; \mathbf{c}(w) = c' ) = \frac{1}{12} \quad (6)</math>
for any distinct <math>c,c' \in \{1,2,3,4\}</math>.  If <math>u</math> is at a unit distance from both z and w, then
:<math> {\bf P}( \mathbf{c}(z) = c; \mathbf{c}(w) = c'; \mathbf{c}(u) = c'' ) = \frac{1}{24} \quad (6')</math>


'''Proof'''  By color invariance (2), the four probabilities in (4) are equal and sum to 1, giving (4).  The claim (5) is immediate from (1).  From (5) and color invariance, the 12 probabilities in (6) are equal and sum to 1, giving (6).  The same argument gives (6').<math>\Box</math>


'''Lemma 2'''  (Spindle argument) Let <math>z,w \in {\bf C}</math> with <math>|z-w| \geq 1/2</math>.  Then
:<math> {\bf P}( \mathbf{c}(z) = \mathbf{c}(w) ) \leq \frac{1}{2} \quad (7).</math>

'''Proof'''  Set <math>d = |z-w|</math>.  We can find an angle <math>\theta</math> with <math>|de^{i\theta}-d|=1</math>, then <math>\mathbf{c}(de^{i\theta}) \neq \mathbf{c}(d)</math> almost surely.  This means that at least one of the events <math>\mathbf{c}(0) = \mathbf{c}(d)</math>, <math>\mathbf{c}(0) = \mathbf{c}(d e^{i\theta})</math> occurs with probability at most 1/2.  The claim now follows from isometry invariance (3). <math>\Box</math>

'''Lemma 3'''  (Using the K graph) We have
:<math>52 {\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) + {\bf P}( \mathbf{c}(-z) = \mathbf{c}(z) \hbox{ for } z = 2, 2e^{2\pi i/3}, 2e^{4\pi i/3} ) \geq 1 \quad (8).</math>

'''Proof''' Consider the 61-vertex graph <math>K</math> from [https://arxiv.org/abs/1804.02385 de Grey's paper].  It has 26 (isometric) copies of H, and thus 52 copies of the triangle <math>(1, e^{2\pi i/3}, e^{4\pi i/3})</math>.  With probability at least <math>1 - 52 {\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) </math>, none of these triangles are monochromatic.  By the argument in that paper, this implies that the three linking diagonals <math>(-2, +2)</math>, <math>(-2 e^{2\pi i/3}, 2e^{2\pi i/3})</math>, <math>(-2 e^{4\pi i/3}, e^{-4\pi i/3})</math> are monochromatic.  This gives the claim. <math>\Box</math>

'''Corollary 4'''  (Existence of monochromatic <math>\sqrt{3}</math>-triangles) We have <math>{\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) \geq \frac{1}{104}</math>.

'''Proof''' The probability <math>{\bf P}( \mathbf{c}(-z) = \mathbf{c}(z) \hbox{ for } z = 2, 2e^{2\pi i/3}, 2e^{4\pi i/3} )</math> is at most <math>{\bf P}( \mathbf{c}(-2) = \mathbf{c}(2))</math>, which by Lemma 2 is at most 1/2.  The claim now follows from Lemma 3.  <math>\Box</math>

'''Computer-verified Claim 5'''  (Using the graph M)  One has <math>{\bf P}( \mathbf{c}(1) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) = 0</math>  (Note this contradicts Corollary 4).

'''Proof''' This simply reflects the fact that there is no 4-coloring of the 1345-vertex graph M from [https://arxiv.org/abs/1804.02385 de Grey's paper] with its central copy of H containing a monochromatic triangle.  One can use other graphs for this purpose, such as the 278-vertex graph <math>M_1</math> or <math>V \oplus V \oplus H</math>. <math>\Box</math>

'''Computer-verified Claim 6'''  (Using the graph <math>V \oplus V \oplus H</math>)  One has <math> {\bf P}( \mathbf{c}(0) = \mathbf{c}(8/3) ) = 1</math> (note this contradicts Lemma 2).

'''Proof''' This reflects the fact that every 4-coloring of <math>V \oplus V \oplus H</math> must assign the same color to 0 and 8/3.  There is also a 745-vertex subgraph of <math>V \oplus V \oplus H</math> with the same property. <math>\Box</math>

'''Lemma 7''' (Using <math>G_{40}</math>)  We have
:<math>59 {\bf P}( \mathbf{c}(0) = \mathbf{c}(\sqrt{11/3}) ) + {\bf P}( \mathbf{c}(0) = \mathbf{c}(8/3) ) \geq 1</math>.

'''Proof''' This reflects the fact that every 4-coloring of the 40-vertex graph <math>G_{40}</math> from [https://arxiv.org/abs/1805.00157 Exoo-Ismaolescu] in which none of the 59 pairs of vertices at distance <math>\sqrt{11/3}</math> apart, will assign the same color to 0 and 8/3.   (This is presumably human-verifiable.) <math>\Box</math>

'''Corollary 8''' One has
:<math>{\bf P}( \mathbf{c}(0) = \mathbf{c}(\sqrt{11/3}) ) \geq \frac{1}{118}</math>.

'''Proof''' Combine Lemma 7 and Lemma 2.  <math>\Box</math>

'''Lemma 9''' (Using <math>G_{49}</math>) One has
:<math>18 {\bf P}( \mathbf{c}(1/3) = \mathbf{c}(e^{2\pi i/3}/3) = \mathbf{c}(e^{4\pi i/3}/3) )  \geq {\bf P}( \mathbf{c}(0) = \mathbf{c}(\sqrt{11/3}) ).</math>

'''Proof'''  This reflects the fact that every 4-coloring of the 49-vertex graph <math>G_{49}</math> from [https://arxiv.org/abs/1805.00157 Exoo-Ismaolescu] in which 0 and <math>\sqrt{11/3}</math> have the same color, at least one of the 18 copies of <math>(1/3, e^{2\pi i/3}/3, e^{4\pi i/3}/3)</math> is monochromatic.  This is potentially human-verifiable. <math>\Box</math>

'''Corollary 10''' (Existence of monochromatic <math>1/\sqrt{3}</math>-triangles) One has <math>{\bf P}( \mathbf{c}(1/3) = \mathbf{c}(e^{2\pi i/3}/3) = \mathbf{c}(e^{4\pi i/3}/3) ) \geq \frac{1}{2124}.</math>

'''Proof''' Combine Corollary 8 and Lemma 9. <math>\Box</math>

'''Computer-verified claim 11'''  One has <math>{\bf P}( \mathbf{c}(1/3) = \mathbf{c}(e^{2\pi i/3}/3) = \mathbf{c}(e^{4\pi i/3}/3) ) = 0</math>.  (This contradicts Corollary 10).

'''Proof''' This reflects the fact that the 627-vertex graph <math>G_{627}</math> from [https://arxiv.org/abs/1805.00157 Exoo-Ismaolescu] does not have any 4-colorings with <math>1/3, e^{2\pi i/3}/3, e^{4\pi i/3}/3</math> monochromatic. <math>\Box</math>

For certain special distances d, one can improve the bound in Lemma 2:

'''Lemma 12''' If <math>k \geq 1</math> is a natural number, <math>j\in\mathbb{Z}</math>, and <math>\gcd(j,2k+1)=1</math> then
:<math> {\bf P}( {\mathbf c}( 0) = {\mathbf c}( \frac{1}{2 \sin \frac{j\pi}{2k+1}} ) ) \leq \frac{k}{2k+1},</math>
thus for instance
:<math> {\bf P}( {\mathbf c}(0) = {\mathbf c}(\frac{1}{\sqrt{3}}) ) \leq \frac{1}{3}.</math>

'''Proof''' Write <math>r = \frac{1}{2 \sin \frac{j\pi}{2k+1}}</math>, then observe that the regular 2k+1-polygon <math>r, re^{2\pi i/(2k+1)}, r e^{4\pi i/(2k+1)}, \dots, r^{4k\pi i/(k+1)}</math> has unit side lengths.  By the pigeonhole principle, we conclude that at most k of these vertices can have the same color as the origin, and the claim follows. <math>\Box</math>

On the other hand, for <math>k=2</math> we also know from the regular pentagon that 
:<math> {\bf P}( {\mathbf c}(0) = {\mathbf c}( \frac{\sqrt{5}-1}{2}) ) \geq \frac{1}{5}</math>
because otherwise we would have an embedded <math> K_5.</math>

'''Lemma 13''' We have
:<math> 7 {\bf P}( {\mathbf c}(0) = {\mathbf c}(\frac{1}{\sqrt{3}}) ) \geq {\bf P}( {\mathbf c}(0) = {\mathbf c}(\sqrt{3}) )</math>.

'''Proof'''  Consider the unit rhombus <math>0, 1, e^{i\pi/3}, e^{-i\pi/3}</math> together with the centers <math>e^{i\pi/6}/\sqrt{3}, e^{-i\pi/6}/\sqrt{3}</math>.  With probability <math>{\bf P}( {\mathbf c}(0) = {\mathbf c}(\sqrt{3}) )</math>, the two far vertices <math>e^{i\pi/3}, e^{-i\pi/3}</math> are the same color, and then 0,1 will be two other colors.  This forces either one of the centers <math>e^{i\pi/6}/\sqrt{3}</math> of a triangle to have a common color with one of the vertices of that triangle, or the two centers must have the same color.  Thus in any event one of the seven edges of distance <math>1/\sqrt{3}</math> is monochromatic, giving the claim. <math>\Box</math>

'''Corollary 14'''  We have <math>{\bf P}( {\mathbf c}(0) = {\mathbf c}(\frac{1}{\sqrt{3}}) ) \geq \frac{1}{728}</math>.

This slightly improves upon the lower bound of 1/2124 coming from Corollary 10.

'''Proof''' Combine Corollary 4 and Lemma 13. <math>\Box</math>

'''Lemma 15''' One has
:<math>{\bf P}( {\mathbf c}(0) = {\mathbf c}(\sqrt{3}) ) + {\bf P} ({\mathbf c}(0) = {\mathbf c}(2) ) \geq \frac{2}{3}</math> and <math>2{\bf P}( {\mathbf c}(0) = {\mathbf c}(\sqrt{3}) ) + {\bf P} ({\mathbf c}(0) = {\mathbf c}(2) ) \geq 1</math>.

'''Proof''' As noted in de Grey's paper, there are essentially four 4-colorings of H.  H has six edges of length <math>\sqrt{3}</math> and three of length <math>2</math>.  If we let a denote the number of monochromatic <math>\sqrt{3}</math> edges and b the number of monochromatic <math>2</math>-edges, we see from inspection of all four colorings that <math>(a,b)</math> is either <math>(6, 0), (4,0), (2, 1)</math>, or <math>(0,3)</math>.  In particular, one always has <math>\frac{a}{6} + \frac{b}{3} \geq \frac{2}{3}</math> and <math>2\frac{a}{6} + \frac{b}{3} \geq 1</math>. Taking expectations, we obtain the claim.  <math>\Box</math>

'''Corollary 16'''  We have <math>{\bf P}( {\mathbf c}(0) = {\mathbf c}(2) ) \geq \frac{1}{6}</math>, <math>{\bf P}( {\mathbf c}(0) = {\mathbf c}(\sqrt{3} ) ) \geq \frac{1}{4} </math> and  <math>{\bf P}( {\mathbf c}(0) = {\mathbf c}(\frac{1}{\sqrt{3}}) ) \geq \frac{1}{28}</math>.
 
'''Proof''' Combine Lemma 2, Lemma 15, and Lemma 13. <math>\Box</math>

'''Lemma 17'''  If <math>a,b,c > 0</math> are the lengths of a triangle, then <math>{\bf P}(\mathbf{c}(0)=\mathbf{c}(a)) + {\bf P}(\mathbf{c}(0)=\mathbf{c}(b)) \leq 1 + {\bf P}(\mathbf{c}(0)=\mathbf{c}(c))</math>.

'''Proof''' Consider a triangle of side lengths a,b,c.  If the c side is not monochromatic, then at least one of the other two sides must fail to be monochromatic also, thus
:<math>{\bf P}(\mathbf{c}(0) \neq \mathbf{c}(a)) + {\bf P}(\mathbf{c}(0) \neq \mathbf{c}(b)) \geq {\bf P}(\mathbf{c}(0) \neq \mathbf{c}(c))</math>
and the claim follows. <math>\Box</math>

Note that Lemma 2 follows from the c=1 case of this lemma.  Iterating this lemma starting with Lemma 2 we can also obtain slightly nontrivial upper bounds on <math>{\bf P}(\mathbf{c}(0)=\mathbf{c}(a))</math> for small values of a, e.g. <math>{\bf P}(\mathbf{c}(0)=\mathbf{c}(a)) \leq 3/4</math> when <math>a \geq 1/4</math>.