# Math Help - Binary relation

1. ## Binary relation

Hi

A is a set of 512 binary numbers of 9 bits each.
We say that two elements in A are related if they differ from each other by no more then 2 bits.
We should find a minimal subset of A that cover all A by this relation

2. ## Re: Binary relation

Hey shlosmem1.

Your relation in this case is (Ai XOR Bi) = 1 for some bit position i for less than 2. Basically this is a combinatoric argument where you can have:

0 difference (same numbers)
1 difference (8 possible differences)
2 difference (8C2 possible differences or 28 differences).

This means that for every number you have 1 + 8 + 28 or 37 possible numbers for each input that are "similar".

Can you take it from there?

3. ## Re: Binary relation

(9 bits not 8).

This is embarrassing,
Apparently I was breaking my head on an NPC problem.
Vertex cover - Wikipedia, the free encyclopedia

4. ## Re: Binary relation

Sorry: Change 8Cx with 9Cx and re-do the calculations.

5. ## Re: Binary relation

I am not a specialist in coding theory, but from my web search, this may indeed be a difficult problem. Wikipedia says: "The determination of the minimal size $K_q(n,R)$ of a q-ary R-covering code of length n is a very hard problem. In many cases, only lower and upper bounds are known with a large gap between them." Tables here and here give 16 as the size of the smallest covering code for A, and they refer to research papers.

Originally Posted by shlosmem1
We should find a minimal subset of A that cover all A by this relation
By a "minimal subset", do you mean a subset from which no element can be removed, or a subset with the smallest possible number of elements? (Finding the first may be easier.)

Originally Posted by shlosmem1
Apparently I was breaking my head on an NPC problem.
Vertex cover - Wikipedia, the free encyclopedia
Does not vertex cover correspond to the Hamming distance of 1 instead of 2? And even if it is an NPC problem, there may be an easy solution for this particlar graph.

6. ## Re: Binary relation

1. I meant a subset with the smallest possible number of elements. (According to my calculation the lowest bound is 12 also 16 will do it for my practical needs)
2. You can convert the graph form distance of 2 to distance of 1. (when each vertex has 45 edges ).