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

  • $\begingroup$ 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. $\endgroup$ – Peter Shor Sep 2 '10 at 22:42
  • 1
    $\begingroup$ Yes, the "uniformly bounded" constant can depend on $k$. The number of collections of 4-disjoint sets should be independent on $k$. $\endgroup$ – Mark Sapir Sep 2 '10 at 22:58
  • $\begingroup$ In line 4 there is a typo, where it should read $\lambda$ instead of $4$. $\endgroup$ – Gjergji Zaimi Sep 7 '10 at 14:00
  • 1
    $\begingroup$ Actually for $\lambda=4$ the answer is also unknown. $\endgroup$ – Mark Sapir Sep 21 '10 at 2:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.