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

Let $G, H$ be two infinite connected graphs. Suppose that we can color $G$ and $H$ in $m$ and $n$ colors respectively so that monochromatic clusters (i.e. monochromatic connected components) are of uniformly bounded diameters. Is it possible to color the Cartesian product $G\times H$ in $m+n-1$ colors so that the diameters of monochromatic clusters are bounded. Here $G \times H$ is the graph with vertices $(x,y), x\in G, y\in H$ and $(x,y)$ connected with $(p,q)$ iff either $x=p$ and $y,q$ are adjacent in $H$ or $y=q$ and $x,p$ are adjacent in $G$.

Example. Let $Z_3$ be the graph with vertices $i\in \mathbb{Z}$ and edges $(i,j)$ where $|i-j|\le 3$. It can be colored in 2 colors as follows: color intervals $[10k+1, 10k+5]$, $k\in \mathbb{Z}$, in black and intervals $[10k+6,10(k+1)]$ in white. All monochromatic clusters have diameters 2. Then $Z_3\times Z_3$ can be colored in 3=2+2-1 colors so that all monochromatic clusters have uniformly bounded diameters. The clusters are bricks.

Update The question above turned out to be too easy and not what I wanted to ask. Here is the real question.

Let $G, H$ be two infinite connected graphs. Pick a number $\lambda\ge 1$. Suppose that we can color $G$ and $H$ in $m$ and $n$ colors respectively so that monochromatic $\lambda$-clusters (i.e. maximal subsets $X$ where any two vertices $u,v$ are connected by a monochromatic sequence $u=x_0, x_1, ..., x_k=v$ where the distance between $x_i, x_{i+1}$ is at most $\lambda$) are of uniformly bounded diameters. Is it possible to color the Cartesian product $G\times H$ in $m+n-1$ colors so that the diameters of monochromatic $\lambda$-clusters are bounded. Here $G \times H$ is the graph with vertices $(x,y), x\in G, y\in H$ and $(x,y)$ connected with $(p,q)$ iff either $x=p$ and $y,q$ are adjacent in $H$ or $y=q$ and $x,p$ are adjacent in $G$.

In the first version of the question $\lambda=1$. For an example, consider the graph $\mathbb{Z}$ (a line), and $\lambda=3$.

share|improve this question
    
If David's answer worked before (of which I am unsure), should it not also work here, as to get to a different cluster of the same color one needs lambda + 1 steps "in both directions"? Gerhard "Still Worried At First Version" Paseman, 2012.06.18 –  Gerhard Paseman Jun 18 '12 at 22:55
    
David's proof does not work for $\lambda=2$ even for $G=H=\mathbb{Z}$ because you can switch directions. A fancier reason is that the asymptotic dimension of the plane is 2, so you need 3 colors for almost all $\lambda$. The question asks if the dimension of direct product at scale $\lambda$ is the sum of dimensions of the factors. –  Mark Sapir Jun 19 '12 at 4:01

1 Answer 1

Yes. In fact you only need max$(m, n)$ colors. Let's assume $m \leq n$ (switching $G$ and $H$ if necessary.) Number the colors from 0 to $m - 1$ and 0 to $n - 1$. If $x$ has color $i$ and $y$ has color $j$, then give $(x, y)$ color $i + j$ mod $n$. Then the monochromatic connected components of the cartesian product are the cartesian products of the monochromatic connected components.

share|improve this answer
    
Thank you! You are right! I made the question too easy. I will add an update. –  Mark Sapir Jun 18 '12 at 21:10

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.