Take the 2-minute tour ×

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.

share|improve this question
Aren't you just asking for the size of a set with a certain diameter? –  Yemon Choi Sep 8 '13 at 3:53
Can you do better than the set of all words of weight at most $k/2$? –  Noam D. Elkies Sep 8 '13 at 3:59
@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\}$. –  Robert Israel Sep 8 '13 at 6:56
One term used for these is "anticode". –  Chris Godsil Sep 8 '13 at 11:54

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer


