Difference between revisions of "Probabilistic formulation of Hadwiger-Nelson problem"

From Polymath Wiki
Jump to: navigation, search
Line 1: Line 1:
Suppose 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
+
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>
 
:<math>c(z) \neq c(w) \hbox{ whenever } |z-w| = 1. \quad (1)</math>
Line 33: Line 33:
 
:<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>
 
:<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 graph <math>K</math> from [[https://arxiv.org/abs/1804.02385]] .  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>
+
'''Proof''' Consider the 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>.
 
'''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>.
Line 39: Line 39:
 
'''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>
 
'''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>
+
'''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 M with its central copy of H containing a monochromatic triangle. <math>\Box</math>
+
'''Proof''' This simply reflects the fact that there is no 4-coloring of the 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 <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. <math>\Box</math>

Revision as of 17:48, 3 May 2018

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 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 {\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]

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].

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). [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 graph [math]K[/math] from 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 graph M from de Grey's paper with its central copy of H containing a monochromatic triangle. One can use other graphs for this purpose, such as [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. [math]\Box[/math]