Consider the set $\Sigma^n$ of all binary strings of length $n$.

Consider some set $S_k \subseteq \Sigma^k$ of binary strings of length $k$. We call $S_k$ a `generating set' of $\Sigma^n$ if for any string $s \in \Sigma^n$, there exists a string $s' \in S_k$ such that $s'$ is a (not necessarily contiguous) substring of $s$. For example, the set $\Sigma^3 = \{111, 110, 101, 100, 011, 010, 001, 000 \}$ has a generating set $S_2 = \{11, 00\}$.

What is the smallest possible set $S_{n-1}$ that generates $\Sigma^n$?

  • $\begingroup$ This was already asked either here or at cstheory, sorry, but I don't remember more details. $\endgroup$ – domotorp Nov 23 '13 at 19:30
  • $\begingroup$ A simple lower bound is 2^n/2n . As any two basis elements which have their numbers of 0 bits differ by 2 will generate disjoint sets (and one can easily generalize this condition), I expect ceiling of the lower bound to be acheivable for almost all n. (Actually, the bound can be improved to have the denominator be cn for some c not far from 1. That is the bound to target.) $\endgroup$ – The Masked Avenger Nov 23 '13 at 21:30

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.