2
$\begingroup$

Consider a sphere $S_r(0)$ with center at zero and radius $r$ in the Hamming space $\{0,1\}^n$. We will be interested in covering this sphere with balls of radius $\rho < r$.

We know that there is an optimal covering, i.e. a covering such that $S_r(0) \subseteq \bigcup_{i=1}^{i=k} B_{\rho}(x_i)$ and $|B_r| \cdot Poly(n)\ge k \cdot |B_{\rho}|$.

In analogy with the paper "Good coverings of Hamming spaces with spheres" by Cohen and Frankl (published in Discrete Mathematics, North-Holland, 56 (1985), pages 125-131), let us call a covering good if the set $X$ consisting of the centers of the covering balls satisfies $X = S_r(0) \cap L$, where $L$ is some linear subspace of $\{0,1\}^n$.

Question: Is there a good optimal covering of $S_r(0)$?

Improve this question
$\endgroup$
7
  • $\begingroup$ Is $S_r(x)=\{u \in \{0,1\}^n: d(x,u)=r\}$? $\endgroup$
    – kodlu
    Commented Mar 6, 2015 at 0:53
  • $\begingroup$ @kodlu, yes it is $\endgroup$
    – Alexey Milovanov
    Commented Mar 6, 2015 at 2:00
  • $\begingroup$ Does linear optimal mean as good as any (without linear restriction)? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Mar 7, 2015 at 19:46
  • $\begingroup$ Linear over $\mathbb{F}_2$? $\endgroup$
    – Fedor Petrov
    Commented Mar 7, 2015 at 20:30
  • $\begingroup$ @FedorPetrov yes, I mean $\mathbb{F}_2$ $\endgroup$
    – Alexey Milovanov
    Commented Mar 7, 2015 at 20:51

0

Reset to default

You must log in to answer this question.