Probabilistic formulation of Hadwiger-Nelson problem
This is a part of Polymath16 - for the main page, see Hadwiger-Nelson problem.
Suppose for sake of contradiction that we have a 4-coloring [math]\displaystyle{ c: {\bf C} \to \{1,2,3,4\} }[/math] of the complex plane with no unit edges monochromatic, thus
- [math]\displaystyle{ c(z) \neq c(w) \hbox{ whenever } |z-w| = 1. \quad (1) }[/math]
We can create further such colorings by composing [math]\displaystyle{ c }[/math] on the left with a permutation [math]\displaystyle{ \sigma \in S_4 }[/math] on the left, and with the (inverse of) a Euclidean isometry [math]\displaystyle{ T \in E(2) }[/math] on the right, thus creating a new coloring [math]\displaystyle{ \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]\displaystyle{ S_4 \times E(2) }[/math].
It is a fact that all solvable groups (viewed as discrete groups) are amenable, so in particular [math]\displaystyle{ S_4 \times E(2) }[/math] is amenable. This means that there is a finitely additive probability measure [math]\displaystyle{ \mu }[/math] on [math]\displaystyle{ S_4 \times E(2) }[/math] (with all subsets of this group measurable), which is left-invariant: [math]\displaystyle{ \mu(gE) = \mu(E) }[/math] for all [math]\displaystyle{ g \in S_4 \times E(2) }[/math] and [math]\displaystyle{ E \subset S_4 \times E(2) }[/math]. This gives [math]\displaystyle{ S_4 \times E(2) }[/math] the structure of a finitely additive probability space. We can then define a random coloring [math]\displaystyle{ {\mathbf c}: {\bf C} \to \{1,2,3,4\} }[/math] by defining [math]\displaystyle{ {\mathbf c} := {\mathbf \sigma} \circ c \circ {\mathbf T}^{-1} }[/math], where [math]\displaystyle{ ({\mathbf \sigma},{\mathbf T}) }[/math] is the element of the sample space [math]\displaystyle{ S_4 \times E(2) }[/math]. Thus for any complex number [math]\displaystyle{ z }[/math], the random color [math]\displaystyle{ {\mathbf c}(z) }[/math] is a random variable taking values in [math]\displaystyle{ \{1,2,3,4\} }[/math]. The left-invariance of the measure implies that for any [math]\displaystyle{ (\sigma,T) \in S_4 \times E(2) }[/math], the coloring [math]\displaystyle{ \sigma \circ {\mathbf c} \circ T^{-1} }[/math] has the same law as [math]\displaystyle{ {\mathbf c} }[/math]. This gives the color permutation invariance
- [math]\displaystyle{ {\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]\displaystyle{ z_1,\dots,z_k \in {\bf C} }[/math], [math]\displaystyle{ c_1,\dots,c_k \in \{1,2,3,4\} }[/math], and [math]\displaystyle{ \sigma \in S_4 }[/math], and the Euclidean isometry invariance
- [math]\displaystyle{ {\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]
(In probabilistic language, this means that the random coloring is a stationary process with respect to the action of [math]\displaystyle{ S_4 \times E(2) }[/math]. The extraction of a stationary process from a deterministic object is an example of the Furstenberg correspondence principle.)
Bounds on [math]\displaystyle{ p_d }[/math] for 4-colourings
A class of correlations that is of particular interest is that of vertex pairs at some distance [math]\displaystyle{ d }[/math]. Accordingly, define
- [math]\displaystyle{ p_d := {\bf P}( \mathbf{c}(0) = \mathbf{c}(d) ). }[/math]
| distance | Lower bound | Lower-bounding graph/method | Upper bound | Upper-bounding graph | Notes |
|---|---|---|---|---|---|
| [math]\displaystyle{ \geq 1/2 }[/math] | 1/2 | Spindle | |||
| [math]\displaystyle{ \geq 1/(n \sqrt{3}) }[/math] | [math]\displaystyle{ (3n-2)/3n }[/math] | (n+1)-gon with one edge length [math]\displaystyle{ 1/\sqrt{3} }[/math] and the rest d | |||
| 1 | 0 | Unit edge | 0 | Unit edge | |
| [math]\displaystyle{ \frac{1}{\sqrt{3}} }[/math] | 1/28 | Unit diamond plus centres of triangles, together with H, Corollary 16 | 1/3 | Unit triangle plus its centre | |
| 2 | 1/6 | H, Corollary 16 | 1/2 | Spindle | |
| [math]\displaystyle{ {\sqrt{3}} }[/math] | 1/4 | H, Corollary 16 | 1/2 | Spindle | |
| [math]\displaystyle{ {\frac{\sqrt{5}+1}{2}} }[/math] | 1/5 | regular pentagon with unit side length | 2/5 | regular pentagon with unit side length | |
| [math]\displaystyle{ {\frac{\sqrt{5}-1}{2}} }[/math] | 1/5 | regular pentagon with [math]\displaystyle{ {\frac{\sqrt{5}-1}{2}} }[/math] side length | 2/5 | regular pentagon with [math]\displaystyle{ {\frac{\sqrt{5}-1}{2}} }[/math] side length | |
| [math]\displaystyle{ {\sqrt{11/3}} }[/math] | 1/118 | [math]\displaystyle{ G_{40} }[/math] | 1/2 | Spindle | computer-verified |
| 8/3 | 1 | [math]\displaystyle{ V \oplus V \oplus H }[/math] | 1/2 | Spindle | computer-verified; leads to contradiction |
Bounds on [math]\displaystyle{ {\bf P}( \mathbf{c}(0) = \mathbf{c}(d_1) \mid \mathbf{c}(0) \neq \mathbf{c}(d_0) ) }[/math] for 4-colourings
| [math]\displaystyle{ d_1 }[/math] | [math]\displaystyle{ d_0 }[/math] | Lower bound | Lower-bounding graph | Upper bound | Upper-bounding graph | Notes |
|---|---|---|---|---|---|---|
| [math]\displaystyle{ 1+(-1)^{1/3} }[/math] | [math]\displaystyle{ 2 }[/math] | 1/2 | H | Equals [math]\displaystyle{ p_{\sqrt 3}/(1-p_2) }[/math] | ||
| [math]\displaystyle{ 1+(-1)^{1/3} }[/math] | [math]\displaystyle{ 1+(-1)^{-1/3} }[/math] | 1/2 | H |
Proofs of bounds
One can compute some correlations of the coloring exactly:
Lemma 1
Let [math]\displaystyle{ z,w \in {\bf C} }[/math] with [math]\displaystyle{ |z-w|=1 }[/math]. Then
- [math]\displaystyle{ {\bf P}( \mathbf{c}(z) = c ) = \frac{1}{4}\quad (4) }[/math]
for all [math]\displaystyle{ c=1,\dots,4 }[/math],
- [math]\displaystyle{ {\bf P}( \mathbf{c}(z) = \mathbf{c}(w) ) = 0\quad (5), }[/math]
and
- [math]\displaystyle{ {\bf P}( \mathbf{c}(z) = c; \mathbf{c}(w) = c' ) = \frac{1}{12} \quad (6) }[/math]
for any distinct [math]\displaystyle{ c,c' \in \{1,2,3,4\} }[/math]. If [math]\displaystyle{ u }[/math] is at a unit distance from both z and w, then
- [math]\displaystyle{ {\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]\displaystyle{ \Box }[/math]
Lemma 2
(Spindle argument) Let [math]\displaystyle{ |d| \geq 1/2 }[/math]. Then
- [math]\displaystyle{ p_d \leq \frac{1}{2} \quad (7). }[/math]
Proof We can find an angle [math]\displaystyle{ \theta }[/math] with [math]\displaystyle{ |de^{i\theta}-d|=1 }[/math], then [math]\displaystyle{ \mathbf{c}(de^{i\theta}) \neq \mathbf{c}(d) }[/math] almost surely. This means that at least one of the events [math]\displaystyle{ \mathbf{c}(0) = \mathbf{c}(d) }[/math], [math]\displaystyle{ \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]\displaystyle{ \Box }[/math]
Lemma 3
(Using the K graph) We have
- [math]\displaystyle{ 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]\displaystyle{ K }[/math] from de Grey's paper. It has 26 (isometric) copies of H, and thus 52 copies of the triangle [math]\displaystyle{ (1, e^{2\pi i/3}, e^{4\pi i/3}) }[/math]. With probability at least [math]\displaystyle{ 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]\displaystyle{ (-2, +2) }[/math], [math]\displaystyle{ (-2 e^{2\pi i/3}, 2e^{2\pi i/3}) }[/math], [math]\displaystyle{ (-2 e^{4\pi i/3}, e^{-4\pi i/3}) }[/math] are monochromatic. This gives the claim. [math]\displaystyle{ \Box }[/math]
Corollary 4
(Existence of monochromatic [math]\displaystyle{ \sqrt{3} }[/math]-triangles) We have [math]\displaystyle{ {\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]\displaystyle{ {\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]\displaystyle{ {\bf P}( \mathbf{c}(-2) = \mathbf{c}(2)) = p_4 }[/math], which by Lemma 2 is at most 1/2. The claim now follows from Lemma 3. [math]\displaystyle{ \Box }[/math]
Computer-verified Claim 5
(Using the graph M) One has [math]\displaystyle{ {\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 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]\displaystyle{ M_1 }[/math] or [math]\displaystyle{ V \oplus V \oplus H }[/math]. [math]\displaystyle{ \Box }[/math]
Computer-verified Claim 6
(Using the graph [math]\displaystyle{ V \oplus V \oplus H }[/math]) One has [math]\displaystyle{ p_{8/3} = 1 }[/math] (note this contradicts Lemma 2).
Proof This reflects the fact that every 4-coloring of [math]\displaystyle{ 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]\displaystyle{ V \oplus V \oplus H }[/math] with the same property. [math]\displaystyle{ \Box }[/math]
Lemma 7
(Using [math]\displaystyle{ G_{40} }[/math]) We have
- [math]\displaystyle{ 59 p_{\sqrt{11/3}} + p_{8/3} \geq 1 }[/math].
Proof This reflects the fact that every 4-coloring of the 40-vertex graph [math]\displaystyle{ G_{40} }[/math] from Exoo-Ismaolescu in which none of the 59 pairs of vertices at distance [math]\displaystyle{ \sqrt{11/3} }[/math] apart, will assign the same color to 0 and 8/3. (This is presumably human-verifiable.) [math]\displaystyle{ \Box }[/math]
Corollary 8
One has
- [math]\displaystyle{ p_{\sqrt{11/3}} \geq \frac{1}{118} }[/math].
Proof Combine Lemma 7 and Lemma 2. [math]\displaystyle{ \Box }[/math]
Lemma 9
(Using [math]\displaystyle{ G_{49} }[/math]) One has
- [math]\displaystyle{ 18 {\bf P}( \mathbf{c}(1/3) = \mathbf{c}(e^{2\pi i/3}/3) = \mathbf{c}(e^{4\pi i/3}/3) ) \geq p_{\sqrt{11/3}} . }[/math]
Proof This reflects the fact that every 4-coloring of the 49-vertex graph [math]\displaystyle{ G_{49} }[/math] from Exoo-Ismaolescu in which 0 and [math]\displaystyle{ \sqrt{11/3} }[/math] have the same color, at least one of the 18 copies of [math]\displaystyle{ (1/3, e^{2\pi i/3}/3, e^{4\pi i/3}/3) }[/math] is monochromatic. This is potentially human-verifiable. [math]\displaystyle{ \Box }[/math]
Corollary 10
(Existence of monochromatic [math]\displaystyle{ 1/\sqrt{3} }[/math]-triangles) One has [math]\displaystyle{ {\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]\displaystyle{ \Box }[/math]
Computer-verified claim 11
One has [math]\displaystyle{ {\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]\displaystyle{ G_{627} }[/math] from Exoo-Ismaolescu does not have any 4-colorings with [math]\displaystyle{ 1/3, e^{2\pi i/3}/3, e^{4\pi i/3}/3 }[/math] monochromatic. [math]\displaystyle{ \Box }[/math]
For certain special distances d, one can improve the bound in Lemma 2:
Lemma 12
If [math]\displaystyle{ k \geq 1 }[/math] is a natural number, [math]\displaystyle{ j\in\mathbb{Z} }[/math], [math]\displaystyle{ \gcd(j,2k+1)=1 }[/math], and [math]\displaystyle{ r = \frac{1}{2} \csc\left(\frac{j\pi}{2k+1}\right) }[/math] then
- [math]\displaystyle{ p_r \leq \frac{k}{2k+1}, }[/math]
thus for instance
- [math]\displaystyle{ p_{\frac{1}{\sqrt{3}}} \leq \frac{1}{3}. }[/math]
Proof Observe that the regular 2k+1-polygon [math]\displaystyle{ 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]\displaystyle{ \Box }[/math]
On the other hand, for [math]\displaystyle{ k=2,j=1 }[/math] we also know from the regular pentagon of unit sidelength that
- [math]\displaystyle{ \frac{1}{5} \leq p_{\frac{\sqrt{5}+1}{2}} \leq \frac{2}{5} \quad (9) }[/math]
since any 4-coloring of that pentagon has either one or two monochromatic diagonals.
Similarly, for [math]\displaystyle{ k=2,j=2 }[/math] we also know from the regular pentagon of [math]\displaystyle{ \frac{\sqrt{5}-1}{2} }[/math] sidelength that
- [math]\displaystyle{ \frac{1}{5} \leq p_{\frac{\sqrt{5}-1}{2}} \leq \frac{2}{5} }[/math]
since any 4-coloring of that pentagon has either one or two monochromatic edges.
Lemma 13
We have
- [math]\displaystyle{ 7 p_{\frac{1}{\sqrt{3}}} \geq p_{\sqrt{3}} }[/math].
Proof Consider the unit rhombus [math]\displaystyle{ 0, 1, e^{i\pi/3}, e^{-i\pi/3} }[/math] together with the centers [math]\displaystyle{ e^{i\pi/6}/\sqrt{3}, e^{-i\pi/6}/\sqrt{3} }[/math]. With probability [math]\displaystyle{ p_{\sqrt{3}} }[/math], the two far vertices [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ 1/\sqrt{3} }[/math] is monochromatic, giving the claim. [math]\displaystyle{ \Box }[/math]
Corollary 14
We have [math]\displaystyle{ p_{\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]\displaystyle{ \Box }[/math]
Lemma 15
One has
- [math]\displaystyle{ p_{\sqrt{3}} + p_2 \geq \frac{2}{3} }[/math] and [math]\displaystyle{ 2 p_{\sqrt{3}} + p_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]\displaystyle{ \sqrt{3} }[/math] and three of length [math]\displaystyle{ 2 }[/math]. If we let a denote the number of monochromatic [math]\displaystyle{ \sqrt{3} }[/math] edges and b the number of monochromatic [math]\displaystyle{ 2 }[/math]-edges, we see from inspection of all four colorings that [math]\displaystyle{ (a,b) }[/math] is either [math]\displaystyle{ (6, 0), (4,0), (2, 1) }[/math], or [math]\displaystyle{ (0,3) }[/math]. In particular, one always has [math]\displaystyle{ \frac{a}{6} + \frac{b}{3} \geq \frac{2}{3} }[/math] and [math]\displaystyle{ 2\frac{a}{6} + \frac{b}{3} \geq 1 }[/math]. Taking expectations, we obtain the claim. [math]\displaystyle{ \Box }[/math]
Corollary 16
We have [math]\displaystyle{ p_2 \geq \frac{1}{6} }[/math], [math]\displaystyle{ p_{\sqrt{3}} \geq \frac{1}{4} }[/math] and [math]\displaystyle{ p_{\frac{1}{\sqrt{3}}} \geq \frac{1}{28} }[/math].
Proof Combine Lemma 2, Lemma 15, and Lemma 13. [math]\displaystyle{ \Box }[/math]
Lemma 17
If [math]\displaystyle{ a,b,c \gt 0 }[/math] are the lengths of a triangle, then [math]\displaystyle{ p_a + p_b \leq 1 + p_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]\displaystyle{ {\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]\displaystyle{ \Box }[/math]
Note that Lemma 2 follows from the a=b, c=1 case of this lemma. Iterating this lemma starting with Lemma 2 we can also obtain slightly nontrivial upper bounds on [math]\displaystyle{ p_a }[/math] for small values of a, e.g. [math]\displaystyle{ p_a \leq 1 - 2^{-k} }[/math] when [math]\displaystyle{ a \geq 2^{-k}, k\in\mathbb{Z}^+ }[/math]. Further, we can generalise the a=b case to one in which the triangle is replaced by a (k+1)-gon of which one edge is 1 and the others are all equal, leading to the stronger result [math]\displaystyle{ p_a \leq 1 - 1/k }[/math] when [math]\displaystyle{ a \geq 1/k, k\in\mathbb{Z}^+ }[/math]. Further strenthening is achieved by using [math]\displaystyle{ 1/\sqrt{3} }[/math] as the long edge, given Lemma 12.
Lemma 18
Whenever [math]\displaystyle{ d\gt 0 }[/math], one has the inequalities
- [math]\displaystyle{ |p_{\phi d} - p_d| \leq \frac{2}{5}, p_{\phi d} + p_d \geq \frac{1}{5}, 2p_d - p_{\phi d} \leq 1, 2 p_{\phi d} - p_d \leq 1 }[/math]
where [math]\displaystyle{ \phi := \frac{1+\sqrt{5}}{2} }[/math] is the golden ratio. Also we have
- [math]\displaystyle{ p_{d/\sqrt{3}} \leq \frac{1}{3} + p_d, \frac{1}{2} + \frac{1}{2} p_d. }[/math]
Note that this generalises (9), as well as a special case of Lemma 12.
Proof Consider the regular pentagon with sidelength [math]\displaystyle{ d }[/math], so it also has 5 diagonals of length [math]\displaystyle{ \phi d }[/math]. Let [math]\displaystyle{ a \in \{0,1,2,3,4,5\} }[/math] denote the number of monochromatic edges and let [math]\displaystyle{ b \in \{0,1,2,3,4,5\} }[/math] denote the number of monochromatic diagonals. Observe:
- [math]\displaystyle{ a,b }[/math] cannot both be zero (pigeonhole principle).
- [math]\displaystyle{ a }[/math] cannot be 4. Similarly, [math]\displaystyle{ b }[/math] cannot be 4.
- If [math]\displaystyle{ a=5 }[/math], then [math]\displaystyle{ b=5 }[/math], and conversely.
- If [math]\displaystyle{ a=0 }[/math], then [math]\displaystyle{ b=1,2 }[/math]; similarly, if [math]\displaystyle{ b=0 }[/math], then [math]\displaystyle{ a=1,2 }[/math].
From this we observe the inequalities
- [math]\displaystyle{ |\frac{a}{5}-\frac{b}{5}| \leq \frac{2}{5}; \frac{a}{5} + \frac{b}{5} \geq \frac{1}{5}; 2 \frac{a}{5} - \frac{b}{5} \leq 1; 2\frac{b}{5} - \frac{a}{5} \leq 1 }[/math]
and on taking expectations we obtain the first claim. Similarly, if one considers the colorings of an equilateral triangle of sidelength [math]\displaystyle{ d }[/math] together with its center, and counts the numbers [math]\displaystyle{ a,b \in \{0,1,2,3\} }[/math] of monochromatic edges of length [math]\displaystyle{ d }[/math] and [math]\displaystyle{ d/\sqrt{3} }[/math] respectively, one observes that one always has [math]\displaystyle{ \frac{b}{3} \leq \frac{1}{3} + \frac{2}{3} \frac{a}{3}, \frac{1}{2} + \frac{1}{2} \frac{a}{3} }[/math], and on taking expectations one obtains the claim.[math]\displaystyle{ \Box }[/math]
The hexagon [math]\displaystyle{ H }[/math] has essentially four distinct colorings: the coloring [math]\displaystyle{ \hbox{2tri} }[/math] with two triangles, the coloring [math]\displaystyle{ \hbox{1tri} }[/math] with one triangle, the coloring [math]\displaystyle{ \hbox{axisym} }[/math] that is symmetric around an axis, and the coloring [math]\displaystyle{ \hbox{centralsym} }[/math] that is symmetric around the central point. This gives four probabilities [math]\displaystyle{ p_{H = 2tri}, p_{H = 1tri}, p_{H = axisym}, p_{H = centralsym} }[/math] that sum to 1. By counting the number of monochromatic edges of length [math]\displaystyle{ \sqrt{3}, 2 }[/math] respectively, one also obtains the identities
- [math]\displaystyle{ p_{\sqrt{3}} = p_{H = 2tri} + \frac{2}{3} p_{H = 1tri} + \frac{1}{3} p_{H = axisym}; \quad p_2 = \frac{1}{3} p_{H=axisym} + p_{H=centralsym} }[/math]
which reproves Lemma 15. Also
- [math]\displaystyle{ {\bf P}( \mathbf{c}(0) = \mathbf{c}(e^{2\pi i/3}) = \mathbf{c}(e^{4\pi i/3}) ) = p_{H = 2tri} + \frac{1}{2} p_{H=1tri}. }[/math]
Any 4-coloring of L contains at least one triangle within one of its 52 copies of H, thus
- [math]\displaystyle{ p_{H = 2tri} + \frac{1}{2} p_{H=1tri} \geq \frac{1}{52} }[/math]
which reproves Corollary 4.
Lemma 19
(Hubai) One has [math]\displaystyle{ p_{H = 1tri} + p_{H = axisym} \geq \frac{1}{10} }[/math].
Proof Consider five copies of H centred at 0,1,2,3,4. With probability at least [math]\displaystyle{ 1 - 5( p_{H = 1tri} + p_{H = axisym} ) }[/math], none of these copies of H are colored 1tri or axisym, and so must be colored 2tri or centralsym. One can check then that if one of the copies is colored 2tri, then so is any adjacent copy; thus all five copies are colored 2tri, or all five are colored centralsym. In either case we see that -1 and 5 are colored the same color. Comparing with Lemma 2 then gives the claim. [math]\displaystyle{ \Box }[/math]
Theorem 20
One has [math]\displaystyle{ p_{H = 1tri} \gt 0 }[/math].
Proof Suppose for contradiction that [math]\displaystyle{ p_{H = 1tri} = 0 }[/math]. One can then run a version of the de Bruijn-Erdos argument to obtain a coloring in which 1tri hexagons are completely nonexistent (since there are arbitrarily large finite colorings with this property). Consider the triangular lattice [math]\displaystyle{ {\bf Z}[e^{\pi i/3}] }[/math]. We consider the dual graph, in which each element of the triangular lattice is the center of a hexagon in the dual graph, which is dual to the copy of H centered at that element. Color an edge [math]\displaystyle{ e^\perp }[/math] in the dual lattice black if the original edge [math]\displaystyle{ e }[/math] is monochromatic, and white otherwise. Thus, each hexagon has one of three coloring patterns up to rotation, depending on the coloring type of H:
- If H is colored 2tri, then all six edges of the hexagon are black.
- If H is colored axisym, then two opposing edges of the hexagon are black, and the other two are white.
- If H is colored centralsym, then none of the edges of the hexagon are black.
In particular, if one hexagon is colored 2tri, then either all adjacent hexagons are colored 2tri, or else all adjacent hexagons are colored axisym. If one follows an axisym hexagon along its axis of symmetry, the adjacent hexagons are either again axisym, or 2tri; thus, one either gets an infinite chain of axisym hexagons, a ray of axisym hexagons terminating at a 2tri hexagon, or an interval of axisym hexagons terminated at both sides by a 2tri hexagon. In the latter case one can continue the coloring to find that the 2tri hexagons are arranged in a lattice, with consecutive 2tri hexagons joined by chains of axisym hexagons. This leads to only a small number of possible hexagon colorings in the lattice:
- Case 1: Every hexagon centred at an element [math]\displaystyle{ {\bf Z}[ e^{\pi i/3} ] }[/math] is colored centralsym.
- Case 2: Every hexagon centred at an element [math]\displaystyle{ {\bf Z}[ e^{\pi i/3} ] }[/math] is colored 2tri.
- Case 3.k: For some natural number [math]\displaystyle{ k \geq 2 }[/math], every hexagon centred in a coset of [math]\displaystyle{ k \cdot {\mathbf Z}[ e^{\pi i/3} ] }[/math] is colored 2tri, the hexagons connecting any two adjacent hexagons in this coset are colored axisym, and all other hexagons are colored centralsym.
- Case 4: Each horizontal row of hexagons either consists entirely of centralsym, or consists entirely of axisym (with the axis of symmetry horizontal).
- Case 5: Each northwest row of hexagons consists either entirely of centralsym, or consists entirely of axisym (with axis of symmetry northwest).
- Case 6: Each northeast row of hexagons consists either entirely of centralsym, or consists entirely of axisym (with axis of symmetry northeast).
- Case 7: A single hexagon colored 2tri, with six rays of hexagons colored axisym emanating from this hexagon; all other triangles are centralsym.
Technically, Case 1 is contained in Cases 4,5,6 as written above, but this will not be an issue.
In the first case, the coloring is periodic with periods [math]\displaystyle{ 2, 2 e^{\pi i/3} }[/math]. In the second case, it is periodic with periods [math]\displaystyle{ 3, 3 e^{\pi i/3} }[/math]. In the third case, it is periodic with periods [math]\displaystyle{ 3k, 3k e^{\pi i/3} }[/math]. Also note that for each k, one can check if Case 3.k holds by inspecting the coloring at a finite number of vertices. Thus the event that Case 3.k holds is "measurable" in the sense that a meaningful probability can be assigned. (But Cases 1,2,4,5,6 are not measurable events, they require an infinite number of points to be inspected, and the probability measure we are using is only finitely additive rather than infinitely additive.) In Case 4, the coloring is periodic with period 2; also, every coset of [math]\displaystyle{ 2 \cdot {\bf Z}[e^{\pi i/3}] }[/math] is 2-colored. Similarly for Case 5 and 6 (where the periods are [math]\displaystyle{ 2 e^{2\pi i/3} }[/math] and [math]\displaystyle{ 2 e^{4\pi i/3} }[/math] respectively.)
Let [math]\displaystyle{ \alpha_k }[/math] be the probability that Case 3.k holds for the given value of [math]\displaystyle{ k }[/math]. Then [math]\displaystyle{ \sum_{k=2}^K \alpha_k \leq 1 }[/math] for any k, hence [math]\displaystyle{ \sum_{k=2}^\infty \alpha_k \leq 1 }[/math]. In particular, we can find [math]\displaystyle{ K_1 }[/math] such that [math]\displaystyle{ \sum_{k={K_1}}^\infty \alpha_k \leq 0.1 }[/math] (say). Let [math]\displaystyle{ P }[/math] be six times the least common multiple of [math]\displaystyle{ 1,2,\dots,K_1 }[/math]. Then the coloring is P- and [math]\displaystyle{ P e^{\pi i/3} }[/math]-periodic for Case 1, Case 2, and all Case 3.k with [math]\displaystyle{ k \leq K_1 }[/math]. On the other hand, if [math]\displaystyle{ K_2 }[/math] is sufficiently large depending on [math]\displaystyle{ P }[/math], and Case 3.k holds for some [math]\displaystyle{ k \geq K_2 }[/math], then almost all of the hexagons are colored centralsym, which makes the coloring "almost [math]\displaystyle{ P, P e^{\pi i/3} }[/math]-periodic" in the sense that
- [math]\displaystyle{ {\bf c}(z+P e^{\pi i j/3}) = {\bf c}(z) \hbox{ for } j=0,1,2,3,4,5 }[/math]
will hold for at least [math]\displaystyle{ 0.9 }[/math] of the lattice points [math]\displaystyle{ z \in {\bf Z}[e^{\pi i/3}] }[/math] with [math]\displaystyle{ |z| \leq K_2 }[/math]. Similarly for Case 7 (which is sort of a [math]\displaystyle{ k=\infty }[/math] limiting case of Case 3.k.) Thus, with the probability [math]\displaystyle{ \geq 1 - \sum_{k=K_1}^{K_2} \alpha_k \geq 0.9 }[/math], the coloring of the seven vertices [math]\displaystyle{ {\bf c}(0), {\bf c}(P e^{\pi ij/3}, j=1,\dots,6 }[/math] is (up to rotation and recoloring) one of the three patterns of the central and linking vertices in Figure 3 of Aubrey's paper, namely
- [math]\displaystyle{ {\bf c}(0) = {\bf c}(P) = {\bf c}(P e^{\pi i/3}) = {\bf c}(P e^{2\pi i/3}) = {\bf c}(P e^{3\pi i/3}) = {\bf c}(P e^{4\pi i/3}) = {\bf c}(P e^{5\pi i/3}) }[/math];
- [math]\displaystyle{ {\bf c}(0) = {\bf c}(P') = {\bf c}(P' e^{3\pi i/3}) }[/math]; [math]\displaystyle{ {\bf c}(P' e^{\pi i/3}) = {\bf c}(P' e^{2\pi i/3}) = {\bf c}(P' e^{4\pi i/3}) = {\bf c}(P' e^{5\pi i/3}) }[/math] for some [math]\displaystyle{ P' = P e^{\pi i j/3} }[/math], [math]\displaystyle{ j=1,\dots,6 }[/math];
- [math]\displaystyle{ {\bf c}(0) = {\bf c}(P') = {\bf c}(P' e^{\pi i/3}) = {\bf c}(P' e^{2\pi i/3}) = {\bf c}(P' e^{3\pi i/3}) }[/math]; [math]\displaystyle{ {\bf c}(P' e^{4\pi i/3}) = {\bf c}(P' e^{5\pi i/3}) }[/math] for some [math]\displaystyle{ P' = P e^{\pi i j/3} }[/math], [math]\displaystyle{ j=1,\dots,6 }[/math].
Using the spindling argument from Aubrey's paper, we conclude that the third possibility must in fact hold with probability at least 0.8; on the other hand, from Lemma 2 this scenario can only occur with probability at most 1/2, giving the required contradiction. [math]\displaystyle{ \Box }[/math]
One should be able to refine this argument to show that [math]\displaystyle{ p_{H = 1tri} \gt c }[/math] for an absolute constant [math]\displaystyle{ c\gt 0 }[/math].
Lemma 21
Providing a tighter bound for Lemma 17 with a more thorough proof: If [math]\displaystyle{ a,b,c \gt 0 }[/math] are the lengths of a triangle, then [math]\displaystyle{ {\bf P}\left(\mathbf{c}(a)\neq \mathbf{c}(0)\neq \mathbf{c}\left(b\exp\left(i\arccos\left(\frac{a^b+b^2-c^2}{2ab}\right)\right)\right) \right) + p_a + p_b \leq 1 + p_c }[/math].
Proof Consider a triangle of side lengths [math]\displaystyle{ a,b,c }[/math]. Let [math]\displaystyle{ \left|z_2\right|=b,\left|a-z_2\right|=c }[/math]. If the c side is not monochromatic, then at least one of the other two sides must fail to be monochromatic also: [math]\displaystyle{ \mathbf{c}(a)\neq\mathbf{c}(z_2)\Rightarrow[\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)] }[/math]. [math]\displaystyle{ [A\Rightarrow B]\Rightarrow {\bf P}(A)\leq{\bf P}(B) }[/math] thus
- [math]\displaystyle{ {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)) \geq {\bf P}(\mathbf{c}(a) \neq \mathbf{c}(z_2)) = 1-p_c }[/math]
[math]\displaystyle{ {\bf P}(A\lor B) +{\bf P}(A\land B)={\bf P}(A)+{\bf P}(B) }[/math], so
- [math]\displaystyle{ {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)) = {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)) + {\bf P}(\mathbf{c}(0)\neq\mathbf{c}(z_2)) - {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\neq\mathbf{c}(z_2)) }[/math]
- [math]\displaystyle{ {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\lor\mathbf{c}(0)\neq\mathbf{c}(z_2)) = 2 - p_a - p_b - {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\neq\mathbf{c}(z_2)) }[/math]
- [math]\displaystyle{ 1-p_c \leq 2 - p_a - p_b - {\bf P}(\mathbf{c}(a)\neq\mathbf{c}(0)\neq\mathbf{c}(z_2)) }[/math]
Using the law of cosines: [math]\displaystyle{ z_2=b\exp\left(i\arccos\left(\frac{a^b+b^2-c^2}{2ab}\right)\right) }[/math]
- [math]\displaystyle{ {\bf P}\left(\mathbf{c}(a)\neq \mathbf{c}(0)\neq \mathbf{c}\left(b\exp\left(i\arccos\left(\frac{a^b+b^2-c^2}{2ab}\right)\right)\right) \right) + p_a + p_b \leq 1 + p_c }[/math] [math]\displaystyle{ \Box }[/math]
Simplification rules for triplets of points in the complex plane
Deduced from the rule [math]\displaystyle{ {\bf P}(A\land B)+{\bf P}(A\land \lnot B)={\bf P}(A) }[/math].
- [math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) = {\mathbf c}(z_2) ) + {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) = {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) ) }[/math]
- [math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) + {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) = {\mathbf c}(z_2) ) = {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) ) }[/math]
- [math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) = {\mathbf c}(z_2) ) - {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) = {\bf P}( {\mathbf c}(z_0) = {\mathbf c}(z_1) ) - {\bf P}( {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) }[/math]
- [math]\displaystyle{ {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) \neq {\mathbf c}(z_0) ) + {\bf P}( {\mathbf c}(z_1) \neq {\mathbf c}(z_2) = {\mathbf c}(z_0) ) = {\bf P}( {\mathbf c}(z_0) \neq {\mathbf c}(z_1) \neq {\mathbf c}(z_2) ) }[/math]
Proofs of bounds for conditional probabilities
The trivial case, valid where [math]\displaystyle{ \left|d\right|\neq 1 }[/math]:
- [math]\displaystyle{ x\in\mathbb{R}\Rightarrow{\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) \mid {\mathbf c}(0) = {\mathbf c}(d) )=0 }[/math]
Trivial plus Baye's Theorem, valid where [math]\displaystyle{ d\neq 0 }[/math]:
- [math]\displaystyle{ x\in\mathbb{R}\Rightarrow{\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) \mid {\mathbf c}(0) \neq {\mathbf c}(d) )=\frac{{\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) )}{1-{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )}\leq 1 }[/math]
Rearrange:
- [math]\displaystyle{ {\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{ix}) )+{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )\leq 1 }[/math]
Spindle method: for [math]\displaystyle{ \left|d\right|=d\geq 1/2 }[/math] and [math]\displaystyle{ \theta=2\text{arcsin}\left(\frac{1}{2d}\right) }[/math]:
- [math]\displaystyle{ {\bf P}( {\mathbf c}(0) = {\mathbf c}(d+e^{i\theta}) \mid {\mathbf c}(0) \neq {\mathbf c}(d) ) = \frac{1}{1-{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )} - 1\leq 1 }[/math]
which is another way to see [math]\displaystyle{ \left|d\right|=d\geq 1/2\Rightarrow{\bf P}( {\mathbf c}(0) = {\mathbf c}(d) )\leq 1/2 }[/math].
