# coloring ${\mathbb Z}^k$

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?

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:

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

Update 3. As is mentoned above, 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?

• You mean $k>1$ right? If so, what about considering the spheres centered at the origin of radius $10n$ dividing $\mathbb Z^k$ into regions of two colors, alternating? Every monochromatic 3-path would be bounded. Jan 22 '11 at 13:56
• No, for $k=1$, $\lt k+1$ means coloring in 1 color. Then there exists an even infinite 1-path. About the second, you are right. I need to restate the question.
– user6976
Jan 22 '11 at 14:04
• Sorry for being dense, but by looking at the lemma, I understand that you have a proof for $k\le 4$ that every $k$ coloring of $\mathbb Z^k$ has arbitrarily large monochromatic 2-paths, and you ask if this property still holds for $k>4$, am I correct? Mar 15 '11 at 10:00
• @Gjegji: Yes, you are correct. In fact I do not know if coloring in constant number of colors without arbitrary long monochromatic 2-paths is possible either.
– user6976
Mar 15 '11 at 10:24
• I deleted what I wrote earlier, it seems it's not that hard to come up with graphs quasi isometric to $\mathbb Z^2$ which can be 2-colored and have bounded monochromatic 2-paths. I now think that this property is also dependent on the vertex degrees in a crucial manner. Mar 16 '11 at 5:44