Minimum number of permutations of $\{1,\ldots, n\}$ that together contain every $k$-subpermutation

Question

Define a $k$-permutation of $\{1,\ldots, n\}$ to be a word $\tau_1 \ldots \tau_k$ such that $\{\tau_1,\ldots,\tau_k\}$ is a $k$-subset of $\{1,\ldots, n\}$. Thus an $n$-permutation of $\{1,\ldots, n\}$ is a permutation written in one-line form. Given a $k$-permutation $\tau$ and a permutation $\sigma$ of $\{1,\ldots, n\}$, say that $\sigma$ contains $\tau$ if there exist positions $i_1 < \ldots < i_k$ such that $\sigma_{i_1} = \tau_1, \ldots, \sigma_{i_k} = \tau_k$.

For $k \le n$, let $f_k(n)$ be the minimum $m$ such that there exist permutations $\sigma^{(1)}, \ldots, \sigma^{(m)}$ of $\{1,\ldots, n\}$ that taken together contain every $k$-permutation of $\{1,\ldots, n\}$.

What is known about the asymptotics of $f_k(n)$ as $n \rightarrow \infty$?

It's easy to see that $f_k(n) \ge k!$ for all $n \ge k$, and that $f_2(n) = 2$ for all $n \ge 2$: just take $\sigma^{(1)} = 12\ldots n$ and $\sigma^{(2)} = n\ldots 21$. Some case-by-case checking shows that $f_3(4) \ge 7$; since

$$1234,4321,3412,2413,3214,1432,4231$$

together contain every $3$-permutation of $\{1,2,3,4\}$, we have $f_3(4) = 7$. A simple greedy algorithm gives the upper bounds

$$f_3(5) \le 8, f_3(6) \le 9, f_3(7) \le 11, f_3(8) \le 12$$

and $f_4(5) = 24$, $f_4(6) \le 36$, $f_4(7) \le 44$, $f_4(8) \le 47$.

What specific values of $f_k(n)$ have been computed and what techniques were used?

Answer 1

Sorry, I do not remember the appropriate reference.

For the lower bound (for $k\geqslant 3$) we may apply the following argument, which uses much less information that is given and in particular does not depend on $k$. We have $m$ permutations, without loss of generality let the first be identical. For each $i=0,1,2,\dots,m-1$ we inductively construct a set $A_i\subset A_{i-1}\subset A_0:=\{1, \ldots, n-1\} $ such that $|A_i|\geqslant 2^{-i}(n-1)$ and the whole $A_i$ is on the same side of the element $n$ in each of permutations $\pi_1,\dots,\pi_{i+1}$. If $|A_{m-1}|>1$, we get two elements which are never separated by $n$, a contradiction. Therefore $n-1\leqslant 2^{m-1}$.

For the upper bound, choose $m$ permutations at random independently. The probability that a fixed word of length $k$ is never realized equals $(1-1/k!)^m$. So the total expected number of not-realized words equals $n(n-1)\dots (n-k+1)(1-1/k!)^m$. If it is less than 1, it happens with positive probability that all words are realized. This is so when $m>k\cdot k! \log n$. Applying Lovasz Local Lemma we probably should slightly improve this bound, but the coefficient is still huge.