16
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Gjergji Zaimi Jan 22 '11 at 13:56
  • $\begingroup$ 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. $\endgroup$ – Mark Sapir Jan 22 '11 at 14:04
  • $\begingroup$ 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? $\endgroup$ – Gjergji Zaimi Mar 15 '11 at 10:00
  • $\begingroup$ @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. $\endgroup$ – Mark Sapir Mar 15 '11 at 10:24
  • $\begingroup$ 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. $\endgroup$ – Gjergji Zaimi Mar 16 '11 at 5:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.