Three dimensional Hadwiger Nelson Problem

251 Views Asked by At

I am interested in Hadwiger Nelson Problem in higher dimensions. In particular, I have seen that the chromatic number for the Hadwiger Nelson Problem in three dimensions is between 6 and 15. But I couldn't find an explanation anywhere. Is this a really obvious result that don't need a proof?

Also, is there an easy lower and upper bound on n dimensions? (Wikipedia gave a lower and upper bound using simplexes and moser spindles but it is a one line explanation which is a bit confusing.)

1

There are 1 best solutions below

8
On BEST ANSWER

I will explain Wikipedia's simplest bounds.

The lower bound of $n+1$ is by taking $n$ points with $\frac1{\sqrt 2}$ in one coordinate, and $0$ in all others, together with the point which is $\frac{1 + \sqrt{n+1}}{n\sqrt 2}$ in each coordinate. For example, when $n=4$, we get the points $(\frac1{\sqrt2}, 0, 0, 0)$, $(0, \frac1{\sqrt2}, 0,0)$, $(0,0, \frac1{\sqrt2}, 0)$, $(0,0,0,\frac1{\sqrt2})$, and $(\frac{1+\sqrt5}{4\sqrt2}, \frac{1+\sqrt5}{4\sqrt2}, \frac{1+\sqrt5}{4\sqrt2}, \frac{1+\sqrt5}{4\sqrt2})$. All $n+1$ of these points are distance $1$ apart, so all of them need different colors.

To get a lower bound of $n+2$, first notice that the point which is $\frac{1 - \sqrt{n+1}}{n\sqrt 2}$ in all coordinates would have been a valid alternative for the $(n+1)^{\text{th}}$ point. If we include both of these points, then we get a configuration of $n+2$ points in which all but two are at distance $1$. Call this configuration an "$n$-dimensional diamond". It has the property that in any $(n+1)$-coloring, the two opposite points must have the same color.

Now take an $n$-dimensional diamond with opposite points $A$ and $B$, and another $n$-dimensional diamond with opposite points $A$ and $B'$: a rotation of the first $n$-dimensional diamond about an axis through $A$. This can be done so that $BB' = 1$. In any $(n+1)$-coloring, $A$ and $B$ have the same color; also, $A$ and $B'$ have the same color. Since $BB'=1$, this is not a proper coloring. So $n+2$ colors are necessary.

Here's a diagram of the two-diamond construction in three dimensions. (In two dimensions it is just the Moser spindle.)

enter image description here


The upper bound generalizes a coloring of the plane where we take a regular square tiling and 9-color it in the pattern

1 2 3 1 2 3 1 2 3 ...
4 5 6 4 5 6 4 5 6 ...
7 8 9 7 8 9 7 8 9 ...
1 2 3 1 2 3 1 2 3 ...
... 

For this tiling to work, the squares must have side length less than $\frac1{\sqrt 2}$ (so that their diagonal lengths are less than $1$) and more than $\frac12$ (so that two closest points in two nearby squares of the same color are more than $1$ apart). Fortunately, $\frac12 < \frac1{\sqrt 2}$, so this works out.

We generalize this by taking a regular hypercube tiling and $k^n$-coloring it, with a pattern that repeats after $k$ steps in any direction. For this tiling to work, the hypercubes must have side length less than $\frac1{\sqrt n}$ (so that their diagonal lengths are less than $1$) and more than $\frac1{k-1}$ (so that two closest points in two nearby hypercubes of the same color are more than $1$ apart). Therefore we require $\frac1{k-1} < \frac1{\sqrt n}$, or $k > 1 + \sqrt n$. Wikipedia sets $k = \lfloor 2 + \sqrt n\rfloor = \lceil 1 + \sqrt{n+1}\rceil$ to make this happen.

Actually, I think that if the hypercubes are defined as translates of $[0,x)^n$, we only need $x \le \frac1{\sqrt n}$ and $x \ge \frac1{k-1}$, not a strict inequality: when $\sqrt n$ is an integer, setting $k = 1 + \sqrt n$ is enough. This shaves off some colors when $n$ is a perfect square.


The upper bounds specific to $3$ dimensions are not easy. For the upper bound of $15$, the paper Note on the chromatic number of the space by Radoičić and Tóth has a construction. The lower bound of $6$ is found in the paper On the space chromatic number by Nechushtan. I will note that Wikipedia cites the first paper, and the first paper cites the second.