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.

anyk columns; not just adjacent columns? $\endgroup$1more comment