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]

For an alternative proof (using another unit-distance graph), see here.

Using bichromatic vertices to bound MCNP

Lemma 2 Let G be a unit distance graph containing the origin such that the origin is not bichromatic. For any 4-coloring [math]\displaystyle{ c }[/math] of the plane, and any non-zero complex number [math]\displaystyle{ z }[/math], let [math]\displaystyle{ \Delta_z }[/math] denote the set of all complex numbers [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ c(v) \neq c(v+z) }[/math]. Then for any [math]\displaystyle{ \theta \in {\bf R} }[/math] and [math]\displaystyle{ v \in \Delta_z }[/math], there exists a non-zero vertex [math]\displaystyle{ w }[/math] of G such that [math]\displaystyle{ v + e^{i\theta} w \in \Delta_z }[/math].

Proof Suppose not, thus there exists [math]\displaystyle{ \theta \in {\bf R}, v \in \Delta_z }[/math] such that [math]\displaystyle{ v + e^{i\theta} w \not \in \Delta_z }[/math] for all non-zero vertices w of G. Then we can 4-color G by giving non-zero vertices w the color of [math]\displaystyle{ c(v + e^{i\theta} w) = c(v + e^{i\theta} w + z) }[/math] and giving the origin the two colors [math]\displaystyle{ c(v) \neq c(v+z) }[/math]. But this contradicts the hypothesis that the origin is not bichromatic. [math]\displaystyle{ \Box }[/math]

Corollary 3 The measurable chromatic number of the plane is at least 5.

Proof Suppose for contradiction that we had a measurable 4-coloring [math]\displaystyle{ c }[/math] of the plane. For any natural number n, consider the set [math]\displaystyle{ \Delta_{1/n} = \{ v: c(v) \neq c(v+1/n) \} }[/math]. These sets are measurable, and their measure in any fixed bounded region tends to zero as [math]\displaystyle{ n \to \infty }[/math] (since translation is strongly continuous in say the [math]\displaystyle{ L^1 }[/math] topology). Also these sets are non-empty, for instance since [math]\displaystyle{ c(0) \neq c(1) }[/math] the pigeonhole principle forces [math]\displaystyle{ \Delta_{1/n} }[/math] to have non-zero intersection with [math]\displaystyle{ \{0, 1/n, 2/n, \dots, (n-1)/n \} }[/math]. Let v_n be an element of [math]\displaystyle{ \Delta_{1/n} }[/math] in [math]\displaystyle{ \{0, 1/n, 2/n, \dots, (n-1)/n \} }[/math], and let G be a finite unit distance graph containing the origin with the origin not bichromatic, such as the one provided by Theorem 1. By two applications of Lemma 2, we see that for any real numbers [math]\displaystyle{ \theta_1,\theta_2 \in [0,2\pi) }[/math], there exist non-zero vertices [math]\displaystyle{ w_1,w_2 }[/math] of G such that [math]\displaystyle{ v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n} }[/math]. By the pigeonhole principle, there thus exists non-zero vertices [math]\displaystyle{ w_1,w_2 \in G }[/math] and a set [math]\displaystyle{ \Omega_n \in [0,2\pi)^2 }[/math] of Lebesgue measure at least [math]\displaystyle{ 1/(|G|-1)^2 }[/math] (where [math]\displaystyle{ |G| }[/math] denotes the number of vertices of G) such that [math]\displaystyle{ v_n + e^{i\theta_1} w_1 + e^{i\theta_2} w_2 \in \Delta_{1/n} }[/math] for all [math]\displaystyle{ (\theta_1,\theta_2) \in \Omega_n }[/math]. Since the map [math]\displaystyle{ (\theta_1,\theta_2) \mapsto e^{i\theta_1} w_1 + e^{i\theta_2} w_2 }[/math] does not depend on [math]\displaystyle{ n }[/math], is at most two-to-one, and is an immersion outside of a measure zero set, we thus conclude that the measure of [math]\displaystyle{ \Delta_{1/n} }[/math] in the disk [math]\displaystyle{ D( 0, 1 + 2 \mathrm{diam}(G) ) }[/math] is bounded away from zero uniformly in n, but this contradicts the strong continuity of translation. [math]\displaystyle{ \Box }[/math]

Conjecture for using bichromatic vertices to bound CNP

Suppose that we have an (embedded) unit-distance graph [math]\displaystyle{ G }[/math] with a special vertex [math]\displaystyle{ v_0 }[/math] that doesn’t admit a 4-coloring if [math]\displaystyle{ v_0 }[/math] has two colors, i.e., none of its neighbors can be red or blue. We want to argue that in this case the chromatic number of the plane is at least 5.

Denote the neighbors of [math]\displaystyle{ v_0 }[/math] by [math]\displaystyle{ \Gamma_0 }[/math]. Consider the [math]\displaystyle{ |\Gamma_0| }[/math] unit circles [math]\displaystyle{ \mathcal C }[/math] that are centered on the points [math]\displaystyle{ \Gamma_0 }[/math] (these all go through [math]\displaystyle{ v_0 }[/math]). We would like to show that for any good (i.e., without a monochromatic unit-distance) 4-coloring of the plane there is an isometric copy of [math]\displaystyle{ \mathcal C }[/math] such that the common points of the circle is, say red, and there is another color, say blue, that is present on all the circles. If we could find such a configuration, then we could just shift [math]\displaystyle{ G }[/math] appropriately so that the vertices [math]\displaystyle{ \Gamma_0 }[/math] are mapped to the centers of the circles.

Conjecture. In any non-monochromatic coloring of the plane with finitely many colors, we can find any such configuration.

The respective conjecture for lines is true: MathOverflow here.