3
$\begingroup$

Imagine the set of all binary vectors of length $2m$ where each of the vectors has $m$ ones and $m$ zeros.
I want to select some $n$ of these vectors such that the shortest distance among all pairs of vectors from this set of $n$ vectors is maximized. In other words I want a set of vectors which are maximally distant from each other.
I define distance by the number of positions at which the corresponding digits are different. For example distance between vectors $[1,0,0,1,1,0]$ and $[1,1,0,0,0,1]$ is $4$.

For example for $m=4$ and $n=2$ the solution can be $[1,1,1,1,0,0,0,0]$ and $[0,0,0,0,1,1,1,1]$.

How can I find a solution for arbitrary $m$ and $n$?

$\endgroup$
11
  • $\begingroup$ I conjecture the problem can be solved by looking at the the smallest $k$ such that $\binom{k}{m}\geq n$, selecting $k$ digits and arbitrarily picking vectors whose only ones are within those $k$ selected digits. $\endgroup$
    – Yorch
    Jan 7 '15 at 17:09
  • 1
    $\begingroup$ There may be something on this in the coding theory literature, since you're asking for a code with maximal error-detecting (or error-correcting) capability, subject to given length, weight, and size of code. $\endgroup$ Jan 7 '15 at 17:24
  • $\begingroup$ @JorgeFernández I don't see it. For example let $m=10$ and $n=5$. Then the smallest $k$ is $11$. Then say we pick the first 11 digits in the vector. Then what do we do? If we select vectors which have all their ones inside those first 11 digits, then all of them will be very close together, but I need them to be far apart. $\endgroup$
    – Sunny88
    Jan 7 '15 at 17:26
  • $\begingroup$ @GerryMyerson Thanks, I added the coding-theory tag. $\endgroup$
    – Sunny88
    Jan 7 '15 at 17:27
  • $\begingroup$ The smallest $k$ would be $7$ since $\binom{7}{5}=21$ $\endgroup$
    – Yorch
    Jan 7 '15 at 17:29
2
$\begingroup$

As Gerry Myerson observed, this is a relatively extensively studied open problem in coding theory. The topic is known as constant-weight codes.

Brouwer has a table of upper bounds for the sizes of constant-weight codes (among other things). In my experience his tables are well maintained, often cited, frequently updated and reflect the current state of research. Wikipedia also gives a link Agrell's table of lower bounds.

$\endgroup$
1
$\begingroup$

Unfortunately I solved the problem of minimizing distances

Let $A$ be a set of $2m$ elements, given a vector of length $2m$ with $m$ ones transform it into a subset of $A$ with $m$ elements where the elements are the positions that have a $1$. given vectors $v$ and $u$ transform them into subsets $v'$ and $u'$. Then the distance between $v$ and $u$ is equal to $2m-|u'\cap v'|$. Then what we want is to find the minimum $t$ so that there is a $t$-intersecting family $\mathcal F\subset \binom{A}{m}$ of size $n$.

You can use Erdős Ko Rado (see result 1.6) which tells you the maximum size of a $t$-intersecting family of subsets of $2m$ of size $m$ is $\binom{2m-t}{m-t}$ when $(m-t+1)(t+1)\geq 2m$, which in this case is for all $t$.

Therefore given $n$ find the largest $t$ so that $\binom{2m-t}{m-t}\geq n$, this is going to be the largest $t$ so that you can find a $t$ intersecting family of size $t$. when you convert the family into vectors you get a family of vectors such that the minimum distance between vectors is $2m-2t$.


The Problem of Maximizing Distances:

For this problem you can do the same translation, only this time you want a family of subsets that have small intersection, apparently this is open. The question has been asked before here and it includes an algorithm for constructing such sets.

$\endgroup$

Your Answer

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

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