Fast solution for a combinatorial maximizaton problem

Question

You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 (consisted of not necessarily consecutive bits). Now we have to find the maximum number from the numbers in S so that every pair of numbers is "compatible" and I want an example numbers from S with that maximum. Here is an example of the task:

n = 6; S = { 000000, 000001, 000010, 000011, ..., 111110, 111111 }; The maximum number from the numbers in S with that property is 10. Here is an example: 000000, 000011, 110000, 001100, 010010, 001111, 111100, 110011, 101101, 111111

I tried making some greedy solutions but they aren't working on greater n (and I think they can't be made accurate). When I thought of some graph solutions I reached an NP problem (let each binary number is vertex and we have an edge connecting them if they aren't "compatible"; now we have to find the maximum in vertices independent set). The other way I tried is making a bipartite graph with one set of vertices with the binary numbers of length n and the other with the binary numbers of length n-1. We have an edge from the first to the second set if the number from the second could be a substring of length n-1 of the number in the first. Now we have to find the maximum number of vertices from the first set so that their edges do not have any common endpoint vertex but I couldn't think out the solution of this problem and couldn't find it in the Internet.

Answer 1

You seem to be looking for the optimal single-deletion-correcting code of length n. As far as I know, it's an open problem.

This paper states that

1. The Varshamov-Tenengolts code (specifically $VT_0$) is a good candidate, but there has been no proof of this as of yet. It is the set of all words for which $\sum_{i=0}^{n} i\cdot x_i \equiv 0 \mod n+1$ where $x_i$ is the $i$-th digit in $x$'s binary representation. Its size can be computed as $$\frac{1}{2(n+1)}\sum_{d\mid n+1 \land 2\not \mid d} \phi(d)2^\frac{n+1}{d}$$. The first few values of the above formula can be found at A000016.

2. The above code has been proven to be optimal for small values of $n$, and to be asymptotically optimal for large $n$.

3. No efficient algorithm has been found to generate/check the optimal code. The largest value of $n$ for which an optimal code is known (and confirmed to be the above) is $9$ (actually $10$).