8
$\begingroup$

The question seems like it should be known, but I was not able to find it anywhere.

How many binary strings of length $n$ are required so that for every $k$ positions in these strings, all $2^k$ possible subsequences occur?

For example, suppose $n=3$, and $k=2$. We want a set of binary strings of length $3$ so that if you look at the first and third symbols (or first two, or last two), you will see all $4$ patterns $00$, $01$, $10$, and $11$. For example, the strings with an even number of $1$s $\{ 000, 011, 110, 101\}$ induce all subsequences on each set of two positions.

Let $f(n,k)$ be the minimum number. Trivially, $f(n,k) \ge 2^k$ so $f(3,2)=4$.

I am interested in precise upper and lower bounds for $f(n,k)$. Bounds that are within a constant of each other (independent of $n$ and $k$) suffice for my purposes.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ The quantifiers are not clear to me. $\endgroup$
    – Anthony Quas
    Commented Aug 31, 2015 at 21:01
  • 1
    $\begingroup$ consider m strings of length n of zeros and ones. Say we arrange them in m rows. Resulting in an $m\times n$ matrix. The question is what is the minimum m so that for every k columns all possible 2^k binary combinations appear in the rows. I am interested in results of the form $f(n,k)\le m \le c f(n,k)$ with c a fixed numerical constant independent of n and k. For example obviously m must be bigger than $2^k$ $\endgroup$
    – Anahita
    Commented Aug 31, 2015 at 21:03
  • $\begingroup$ You are supposed to be able to pick any k columns; not just adjacent columns? $\endgroup$
    – Anthony Quas
    Commented Aug 31, 2015 at 23:40
  • $\begingroup$ I also don't exactly understand what you want, but probably this might help. link $\endgroup$
    – Dongryul Kim
    Commented Aug 31, 2015 at 23:54
  • 2
    $\begingroup$ Can you edit your question to clarify it? It should be understandable for readers who do not look at the comments. $\endgroup$
    – Joonas Ilmavirta
    Commented Sep 1, 2015 at 12:01

2 Answers 2

Reset to default
7
$\begingroup$

Orthogonal arrays were mentioned in another answer, but you are not requiring that each $k$-tuple occurs exactly once in every set of $k$ columns, but rather that each $k$-tuple occurs at least once in every set of $k$ columns.

What you are looking for is called a covering array. In the usual notation for covering and orthogonal arrays, $v$ is the size of the alphabet ($2$ in this case), $k$ corresponds to your $n$, and $t$ corresponds to your $k$. Some known upper bounds for the number of rows for small values of $t,k,v$ are listed in http://www.public.asu.edu/~ccolbou/src/tabby/catable.html - you are interested in the numbers for $(t,k,2)$.

Improve this answer
$\endgroup$
1
$\begingroup$

Definition: A $t-(v,k,\lambda)$ orthogonal array ($t \leq k$) (also called an orthogonal array of power/strength $t$) is a $λv^t × k$ array whose entries are chosen from a set $X$ with $v$ points such that in every subset of $t$ columns of the array, every $t-$tuple of points of $X$ appears in exactly $λ$ rows. I have used the standard notation for letters.

It seems to me the OP is looking for orthogonal arrays with minimal number of rows over the set $X=\{0,1\}$ with $k=n,\lambda=1,$ and $t=k$ because he wants every $k-$tuple to occur in every possible $k$ positions.

There are literally hundreds of papers and tens of constructions in this area. There are some lower bounds known for existence. I suggest he start with reading the Wikipedia entry and then moving on to tutorial papers of which there are plenty. Happy googling!

Improve this answer
$\endgroup$
4
  • $\begingroup$ Also, orthogonal arrays for $\lambda=1$, $v=2$ exist only when $k=t$, $k=t+1$ or $t=1$. $\endgroup$
    – Janne Kokkala
    Commented Sep 1, 2015 at 11:59
  • $\begingroup$ Sorry, fixed. You're right in OA notation his $n$ (length of sequence) is their $k.$ I wasn't aware of the existence restraint you stated. $\endgroup$
    – kodlu
    Commented Sep 1, 2015 at 22:21
  • $\begingroup$ Thanks these are great refs. It seems though orthogonal array means every combination appears exactly once. Is there some thing more specific if we want at least once? $\endgroup$
    – Anahita
    Commented Sep 4, 2015 at 18:16
  • $\begingroup$ @Anahita, you can choose $\lambda\geq 1$ and have everything appear at exactly $\lambda$ times. The other answer is more directly relevant to what you asked. On the other hand, I am unsure if any infinite families of covering arrays are known. $\endgroup$
    – kodlu
    Commented Sep 5, 2015 at 2:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .