3
$\begingroup$

What is the maximum number of pairs of $k\geq2$ distinct binary strings of length $n$, such that the strings in each pair are at Hamming distance $b$? In other words, given $k$ points on the $n$-dimensional Boolean hypercube, how many of these can possibly be at distance $b$ of each other?

I have a trivial upper bound given by $k \min\{\binom{n}{b},k\}$ simply because each string can have at most $\binom{n}{b}$ neighbors at distance $b$. Does anybody know how to better upper bound this quantity?

$\endgroup$
  • $\begingroup$ Do you want all the strings to be pairwise at distance $b$? So for $n=5, b=2$ an answer would be $\{10000,11100,11010,10110\}$? This may not be maximal. $\endgroup$ – Ross Millikan Sep 11 '13 at 15:28
  • $\begingroup$ I think it might not always be possible to have all $k$ strings at pairwise distance $b$ like in your example, because e.g. you cannot have more than $n$ neighbors at distance 1. So I would like to have as many as possible at pairwise distance $b$ $\endgroup$ – adrianomeis Sep 11 '13 at 15:41
  • $\begingroup$ I was trying to understand the question. If I read the first sentence literally, I could split the $2^n$ strings into pairs, with each string at distance $b$ from its mate, and get $2^{n-1} pairs. I don't know for sure this is possible, but I think so. Is that what you are after? $\endgroup$ – Ross Millikan Sep 11 '13 at 15:48
  • $\begingroup$ @Ross' suggestion is easy to make work. Take a fixed string $w$ of weight $b$, and pair up the strings $u$ and $u+b$ for all $u$. Here $u+b$ is the componentwise modulo 2 sum (=bitwise XOR). $\endgroup$ – Jyrki Lahtonen Sep 16 '13 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.