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

This is a question related to covers of $Z^\infty$. Is it possible to cover $Z^k$, $k>1$, with the $l_1$-metric by a constant (not depending on $k$) number of collections of subsets $U^0,...,U^c$ where each $U^i$ consists of uniformly bounded $\lambda$-disjoint sets $U_j^i$ ("$\lambda$-disjoint" means $dist(U_j^i, U_l^i)\ge \lambda$ for every $i,j\not=l$), $\lambda$ is fixed, $>1$?

In http://front.math.ucdavis.edu/1008.3868, we show (Lemma 3.7) that for $k<2^{\lambda-1}$, the minimal $c$ is $k$. The question is what happens for $k\ge 2^{\lambda-1}$.

Update: The answer is not known even if $\lambda=3$.

share|improve this question
Maybe you can clarify the question. Can the constant implicit in "uniformly bounded" depend on $k$? I'm guessing that if it can't, you're left with your previous question. –  Peter Shor Sep 2 '10 at 22:42
Yes, the "uniformly bounded" constant can depend on $k$. The number of collections of 4-disjoint sets should be independent on $k$. –  Mark Sapir Sep 2 '10 at 22:58
In line 4 there is a typo, where it should read $\lambda$ instead of $4$. –  Gjergji Zaimi Sep 7 '10 at 14:00
Thanks, Gjergji, I've fixed that. –  Mark Sapir Sep 7 '10 at 17:44
Actually for $\lambda=4$ the answer is also unknown. –  Mark Sapir Sep 21 '10 at 2:43

Your Answer


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

Browse other questions tagged or ask your own question.