coloring ${\mathbb Z}^k$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T19:34:08Z http://mathoverflow.net/feeds/question/52825 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/52825/coloring-mathbb-zk coloring ${\mathbb Z}^k$ Mark Sapir 2011-01-22T13:40:51Z 2012-04-04T03:09:34Z <p>This question is related to but seems to be simpler than <a href="http://mathoverflow.net/questions/37529/covers-of-zk" rel="nofollow">this one</a>, so perhaps somebody can solve it. </p> <p><b> Question. </b>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. </p> <p>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. </p> <p>We know that if such a $k$ exists, it should be at least $4=2^2$ by Lemma 3.7 in <a href="http://front.math.ucdavis.edu/1008.3868" rel="nofollow">this</a> paper. </p> <p><b> Edit.</b> 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". </p> <p><b> Update 1. </b> 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. </p> <p><b> Update 2. </b> Note that it is not known if a constant (large but independent of $k$) number of colors is always enough: </p> <p>*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. </p> <p><b> Update 3. </b> If we change the metric from $l_1$ to $l_\infty$, then the answer is "no". This follows from the known results about the <a href="http://www.math.pitt.edu/~gartside/hex_Browuer.pdf" rel="nofollow">game of HEX</a>. 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?</p>