# Binary codes with upper bound on pairwise distance

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.

• 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

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.