3
$\begingroup$

A fundamental problem in coding theory is:

Given positive integers $k\le n$, determine or bound the maximal cardinality of a set $S\subset \mathbb{F}_{2}^{n}$ such that $\forall x,y\in S: x\ne y\implies h(x,y)\ge k$, and construct such sets. (Here $h$ is Hamming distance.)

What about the complementary idea? Replace $h(x,y)\ge k$ with $h(x,y)\le k$.

I'm sure these have been explored before, so keywords and references would be appreciated.

$\endgroup$
4
  • $\begingroup$ Aren't you just asking for the size of a set with a certain diameter? $\endgroup$
    – Yemon Choi
    Sep 8, 2013 at 3:53
  • 1
    $\begingroup$ Can you do better than the set of all words of weight at most $k/2$? $\endgroup$ Sep 8, 2013 at 3:59
  • $\begingroup$ @NoamD.Elkies: Slightly better, at least if $k$ is odd. For example, if $k=n-1$, you can get $|S| = 2^{n-1}$ with $S = \{x: x_1 = 0\}$. $\endgroup$ Sep 8, 2013 at 6:56
  • 1
    $\begingroup$ One term used for these is "anticode". $\endgroup$ Sep 8, 2013 at 11:54

2 Answers 2

2
$\begingroup$

The problem you mention is already solved: Rudolf Ahlswede and Levon H. Khachatrian, "The Diametric Theorem in Hamming Spaces—Optimal Anticodes," Advances in Applied Mathematics, Volume 20, Issue 4, May 1998, Pages 429–449.

It turns out that in this case (finite-alphabet vectors and Hamming metric) the result is a cartesian product of a ball and a cube. The problem of determining the size and shape of anticodes in other metric spaces has been studied as well.

$\endgroup$
1
$\begingroup$

You are interested in estimating sizes and constructing independent sets in graphs obtained by merging several classes of the Hamming association scheme $H(n,2)$. That is to say, you consider graphs $H_0$, $H_1$,... $H_n$ on the vertex set $B^n$ of binary $n$-sequences, two vertices of $H_j$ adjacent if the Hamming distance between the corresponding sequences is $j$. In fact you have an edge partition of the complete graph (with loops) on $B^n$, satisfying an extra property that the linear span of the adjacency matrices of the corresponding graphs is closed under multiplication. This basically is a definition of association schemes. What's nice about that that you can use a lot of algebra/algebraic graph theory on them, to obtain various nontrivial bounds.

What you referred to as "a fundamental problem" then becomes a problem about independent sets in the graph $\Gamma_k$ with the vertex set $B^n$ and edges from $H_1$,..., $H_{k-1}$. You can form other graphs from $H_1$,... $H_n$, and/or take other association schemes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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