coloring ${\mathbb Z}^k$

2011-01-22T13:40:51Z

This question is related to but seems to be simpler than this one, so perhaps somebody can solve it.

Question. Is there $k\ge 1$ and a coloring of vertices of the lattice ${\mathbb Z}^k$ in $k$ colors such that there does not exist an arbitrarily long monochromatric simple 2-path? Is there a constant $c$ such that any $\mathbb{Z}^k$, $k\ge 1$, can be colored in $c$ colors without arbitrary long monochromatic simple 2-path.

The metric in ${\mathbb Z}^k$ is $l_1$, a 2-path is a sequence of vertices $v_1,v_2,...$ such that $dist(v_i,v_{i+1})\le 2$. A path is simple if no vertex occurs twice.

We know that if such a $k$ exists, it should be at least $4=2^2$ by Lemma 3.7 in this paper.

Edit. As Gjergji Zaimi noted in his comment, an infinite monochromatic simple 2-path may not exist even if we color in 2 colors. So I restated the question replacing "infinite" by "arbitrary long".

Update 1. Nati Linial and Noga Alon pointed out a connection with the HEX game: if $k$ players color any cube in ${\mathbb Z}^k$ with $l_\infty$-metric with $k$ colors (each player uses his own color), then there always exists a monochromatic 1-path connecting two opposite sides of the cube, that is one player necessarily wins. This is similar to the problem above but a 1-path in the $l_\infty$ metric is a $k$-path in the $l_1$-metric so for 3-paths as above the answer may be different.

Update 2. Note that it is not known if a constant (large but independent of $k$) number of colors is always enough:

*Is it possible to color any ${\mathbb Z}^k$, $k\ge 1$ in $10^{10^{10}}$ colors so that there are no monochromatic $2$-paths.

Update 3. If we change the metric from $l_1$ to $l_\infty$, then the answer is "no". This follows from the known results about the game of HEX. In that text, it is proved, in particular, that the existing a winner in a HEX game is equivalent to the Brouwer fixed point theorem. Can my question above be reformulated as a fixed point theorem too?

coloring ${\mathbb Z}^k$ - MathOverflow

coloring ${\mathbb Z}^k$