Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Gjergji Zaimi 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. –  Mark Sapir 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? –  Gjergji Zaimi 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. –  Mark Sapir 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. –  Gjergji Zaimi Mar 16 '11 at 5:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.