Excluding bichromatic vertices

Theorem 1 A 4-coloring of the unit plane cannot contain a bichromatic vertex (a vertex that can be colored in either of two colors while keeping the color of all other vertices fixed).

Equivalently, in a 4-coloring of the plane, the color of each vertex is determined uniquely by the colors of all the other vertices. This also gives an alternate proof of Falconer's result that the measurable chromatic number of the plane is at least five.

Proof Without loss of generality we may assume that the colors are [math]\displaystyle{ {\bf Z}/4{\bf Z} }[/math] and that the origin is bichromatic with colors 0,2.

Let [math]\displaystyle{ \omega := \exp( i \pi/3) }[/math] be the sixth root of vector, then we have the identities

[math]\displaystyle{ \omega^6 = 1; \quad \omega^3 = -1; \quad \omega^2 = \omega - 1. \quad (1) }[/math]

Let [math]\displaystyle{ \eta := \exp( \frac{i}{2} \arccos(\frac{5}{6})), }[/math] then [math]\displaystyle{ \eta }[/math] is a unit vector that obeys the identity

[math]\displaystyle{ \eta (\omega + \omega^2) - \overline{\eta} (\omega + \omega^2)+ 1 = 0 \quad (2). }[/math]

Let

[math]\displaystyle{ C_6 := \{ \omega^j: j=0,\dots,5\} }[/math]

denote the multiplicative cyclic group of order 6. We consider the coloring of the following seven cosets of [math]\displaystyle{ C_6 }[/math]:

[math]\displaystyle{ C_6, (\eta - \overline{\eta}) C_6, (\eta - \overline{\eta}\omega ) C_6, \eta C_6, (1+\eta\omega^2 ) C_6, \overline{\eta} C_6, (1 + \overline{\eta \omega^2 }) C_6. }[/math]

Clearly [math]\displaystyle{ C_6 }[/math] is conjugation invariant. Since

[math]\displaystyle{ \overline{\eta - \overline{\eta}} = (\eta - \overline{\eta}) \omega^3 }[/math]

[math]\displaystyle{ \overline{\eta - \omega \overline{\eta}} = (\eta - \omega \overline{\eta}) \omega^2 }[/math]

we also see that [math]\displaystyle{ (\eta - \overline{\eta}) C_6 }[/math], [math]\displaystyle{ (\eta - \overline{\eta}\omega) C_6 }[/math] are conjugation invariant, while [math]\displaystyle{ \eta C_6 }[/math] is conjugate to [math]\displaystyle{ \overline{\eta} C_6 }[/math] and [math]\displaystyle{ (1+\eta \omega^2 ) C_6 }[/math] is conjugate to [math]\displaystyle{ (1 + \overline{\eta \omega^2 }) C_6 }[/math].

We observe the following unit edges:

1. Within [math]\displaystyle{ C_6 }[/math], there is a unit edge from any [math]\displaystyle{ \omega^j \in C_6 }[/math] to the origin, to [math]\displaystyle{ \omega^{j+1} \in C_6 }[/math], and [math]\displaystyle{ \omega^{j-1} \in C_6 }[/math].
2. Within [math]\displaystyle{ \eta C_6 }[/math], there is a unit edge from any [math]\displaystyle{ \eta \omega^j \in C_6 }[/math] to the origin, to [math]\displaystyle{ \eta \omega^{j+1} \in \eta C_6 }[/math], and [math]\displaystyle{ \eta \omega^{j-1} \in \eta C_6 }[/math]. Similarly with [math]\displaystyle{ \eta }[/math] replaced by [math]\displaystyle{ \overline{\eta} }[/math].
3. Using (2) (which can be rewritten for instance as [math]\displaystyle{ (\eta - \overline{\eta}) (\omega^2 - 1) = -\omega }[/math]), we see that within [math]\displaystyle{ (\eta - \overline{\eta}) C_6 }[/math], there is a unit edge from any [math]\displaystyle{ (\eta - \overline{\eta}) \omega^j }[/math] to [math]\displaystyle{ (\eta - \overline{\eta}) \omega^{j+2} }[/math] and [math]\displaystyle{ (\eta - \overline{\eta}) \omega^{j-2} }[/math]. In particular, [math]\displaystyle{ (\eta - \overline{\eta}) C_6 }[/math] contains a triangle and thus cannot be 2-colored.
4. Each [math]\displaystyle{ (\eta - \overline{\eta}) \omega^j \in (\eta - \overline{\eta}) C_6 }[/math] has a unit edge to [math]\displaystyle{ (\eta - \overline{\eta} \omega) \omega^j \in (\eta - \overline{\eta} \omega) C_6 }[/math], to [math]\displaystyle{ (\eta - \overline{\eta} \omega) \omega^{j-1} \in (\eta - \overline{\eta} \omega) C_6 }[/math], to [math]\displaystyle{ \eta \omega^j \in \eta C_6 }[/math], to [math]\displaystyle{ -\overline{\eta} \omega^j \in \overline{\eta} C_6 }[/math], to [math]\displaystyle{ \eta \omega^j - \overline{\eta} (\omega^j + \omega^{j+1}) = (1 + \eta \omega^2) \omega^{j+2} \in (1+\eta \omega^2) C_6 }[/math], and to [math]\displaystyle{ \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j = (1+\overline{\eta \omega^2}) \omega^{j+1} \in (1 + \overline{\eta \omega^2}) C_6 }[/math]. (Here (2) is used to obtain the latter two identities.)
5. Each [math]\displaystyle{ (\eta - \overline{\eta} \omega) \omega^j \in (\eta - \overline{\eta} \omega) C_6 }[/math] has a unit edge to [math]\displaystyle{ \eta \omega^j \in \eta C_6 }[/math], to [math]\displaystyle{ -\overline{\eta} \omega^{j+1} \in \overline{\eta} C_6 }[/math], to [math]\displaystyle{ \eta \omega^j - \overline{\eta} (\omega^j + \omega^{j+1}) = (1 + \eta \omega^2) \omega^{j+2} \in (1+\eta \omega^2) C_6 }[/math], and to [math]\displaystyle{ \eta (\omega^{j+1} + \omega^j) - \overline{\eta} \omega^{j+1} = (1+\overline{\eta \omega^2}) \omega^{j+2} \in (1 + \overline{\eta \omega^2}) C_6 }[/math]. (Again, the latter two identities come from (2).)
6. Each [math]\displaystyle{ \omega^j \in C_6 }[/math] has a unit edge to [math]\displaystyle{ \omega^j + \eta \omega^{j+2} \in (1 + \eta \omega^2) C_6 }[/math] and to [math]\displaystyle{ \omega^j + \overline{\eta} \omega^{j-2} \in (1 + \overline{\eta \omega^2}) C_6. }[/math]
7. Each [math]\displaystyle{ \eta \omega^j \in C_6 }[/math] has a unit edge to [math]\displaystyle{ \omega^{j-2} + \eta \omega^j \in (1 + \eta \omega^2) C_6 }[/math]; similarly, each [math]\displaystyle{ \overline{\eta} \omega^j \in C_6 }[/math] has a unit edge to [math]\displaystyle{ \omega^{j+2} + \overline{\eta} \omega^j \in (1 + \overline{\eta \omega^2}) C_6 }[/math].

We will show that [math]\displaystyle{ (\eta - \overline{\eta}) C_6 }[/math] will be forced to be 2-colorable, contradicting item 3 above.

From item 1 and the fact that the origin is colored 0,2 we see that [math]\displaystyle{ C_6 }[/math] is colored 1,3, and in fact the coloring map [math]\displaystyle{ c }[/math] is given by [math]\displaystyle{ c(\omega^j) = c_1 + 2j }[/math] for some [math]\displaystyle{ c_1 = 1,3 }[/math]. Similarly from item 2 we have [math]\displaystyle{ c(\eta \omega^j) = c_\eta + 2j }[/math], [math]\displaystyle{ c(\overline{\eta} \omega^j) = c_{\overline{\eta}} + 2j }[/math] for some [math]\displaystyle{ c_\eta,c_{\overline{\eta}} = 1,3 }[/math].

Suppose first that [math]\displaystyle{ c_\eta = c_{\overline{\eta}} }[/math]. By item 4, each [math]\displaystyle{ (\eta - \overline{\eta})\omega^j }[/math] is connected both to [math]\displaystyle{ \eta \omega^j }[/math] that has color [math]\displaystyle{ c_\eta + 2j }[/math], and to [math]\displaystyle{ -\overline{\eta} \omega^j }[/math] that has color [math]\displaystyle{ c_{\overline{\eta}} + 2j + 2 }[/math]. Thus [math]\displaystyle{ (\eta - \overline{\eta})\omega^j }[/math] has to be colored 0 or 2, giving the 2-coloring of [math]\displaystyle{ (\eta - \overline{\eta}) C_6 }[/math].

Now suppose instead that [math]\displaystyle{ c_\eta \neq c_{\overline{\eta}} }[/math], then [math]\displaystyle{ c_1 }[/math] is distinct from either [math]\displaystyle{ c_\eta }[/math] or [math]\displaystyle{ c_{\overline{\eta}} }[/math]. Without loss of generality (conjugation symmetry) assume [math]\displaystyle{ c_\eta \neq c_1 }[/math]. By item 5, each [math]\displaystyle{ (\eta - \overline{\eta} \omega) \omega^j }[/math] is connected both to [math]\displaystyle{ \eta \omega^j }[/math], which has color [math]\displaystyle{ c_\eta + 2j }[/math], and to [math]\displaystyle{ -\overline{\eta}\omega^{j+1} }[/math], which has color [math]\displaystyle{ c_{\overline{\eta}}+2j }[/math]. Thus all of [math]\displaystyle{ (\eta - \overline{\eta} \omega) C_6 }[/math] is 0,2-colored. Similarly, from items 6,7, each [math]\displaystyle{ \omega^j + \eta \omega^{j+2} }[/math] is connected to [math]\displaystyle{ \omega^j }[/math], which has color [math]\displaystyle{ c_1 + 2j }[/math], and [math]\displaystyle{ \eta \omega^{j+2} }[/math], which has color [math]\displaystyle{ c_\eta + 2j }[/math], and hence [math]\displaystyle{ (1 + \eta \omega^2) C_6 }[/math] is also 0,2-colored. Now observe from items 4,5 that each [math]\displaystyle{ (\eta - \overline{\eta}) \omega^j }[/math] is the vertex of an equilateral triangle with other two vertices [math]\displaystyle{ \eta \omega^{j-1} - \overline{\eta} \omega^j }[/math], [math]\displaystyle{ \eta (\omega^j + \omega^{j-1}) - \overline{\eta} \omega^j }[/math] which are 0,2-colored and hence [math]\displaystyle{ (\eta - \overline{\eta}) C_6 }[/math] is 1,3-colored, again giving the required contradiction. [math]\displaystyle{ \Box }[/math]