19
$\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?

Improve this question
$\endgroup$
9
  • 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
    Commented Jan 22, 2011 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$
    – user6976
    Commented Jan 22, 2011 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
    Commented Mar 15, 2011 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$
    – user6976
    Commented Mar 15, 2011 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
    Commented Mar 16, 2011 at 5:44

0

Reset to default