MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.