Universal words for $k$-permutations

Originator: R. Karp and D. Knuth    (presented by David Galvin - REGS 2011)

Definitions: Let $S_n$ denote the set of permutations of $[n]$. For $1\le k\le n$, let $S_n(k)$ be the set of $k$-permutations from $[n]$, meaning the $k!\binom nk$ permutations of $k$-subsets of $[n]$. A word is a list of elements of $[n]$; here we treat permutations as words. A word $w$ contains a word $\pi$ if the elements of $\pi$ occur somewhere in $w$ in the same order as in $\pi$ (not necessarily consecutively).

Problem 1: Determine the minimum length, $f(n)$, of a word that contains every element of $S_n$.

Problem 2: For $1\le k\le n$, determine the minimum length, $g(n,k)$, of a word that contains every element of $S_n(k)$.

Problem 3: For $1\le m\le n!$, determine the minimum length, $h(n,m)$, of a word that contains at least $m$ elements of $S_n$. (Similarly, one could ask for the shortest word to contain at least $m$ element of $S_n(k)$.)

Background: Problem 1 was posed by Knuth in a 1972 Stanford Computer Science Technical report, where he atributes the problem to Karp. Adleman [A] reports that Karp discovered the problem studying the complexity of some shortest path algorithms. Problem 2 was asked by Savage [S], and Problem 3 seems to be due to Galvin.

Comments: Using $n-1$ repetitions of $1,.~.~.,n$ plus a single $1$ at the end yields $f(n)\leq n^2 -n+1$. Adleman [A] (and many authors around the same time) improved this to $f(n) \leq n^2-2n+4$, proved that this is tight for $n\le7$, and conjectured equality for all $n$. However, Zălinescu [Z] disproved the conjecture, giving a construction to show that $f(n)\le n^2-2n+3$ when $n\ge10$.

For a lower bound, consider a word containing all permutations. It has at least $n$ characters until the last occurrence of a new symbol; let $a$ be that symbol. Subsequently there are at least $n-1$ characters until all pairs starting with $a$ have been seen; let $ab$ be the last. Subsequently there are at least $n-2$ characters until all triples starting with $ab$ have been seen, and so on. Thus $f(n) \geq \binom{n+1}{2}$. Kleitman and Kwiatkowsky improved this to $f(n) \geq (1-o(1))n^2$ (specifically, they showed that for $\varepsilon > 0$ there exist $C(\varepsilon)$ such that $f(n)\geq n^2-C(\varepsilon)n^{7/4+\varepsilon}$).

Savage [S] observed that $g(n,k)\le k(n-2)+4$. For $n\ge k\ge 10$, Zălinescu [Z] improved this to $g(n,k) \leq k(n-2)+3$; we write the upper bound as $kn-(2k-3)$. The argument above for $f(n)\ge\binom{n+1}2$ more generally yields $g(n,k)\ge kn-\binom k2$.

An easy lower bound on $h(n,m)$ is given by ${h(n,m) \choose n}\geq m$. When $m=1$ or $m=n!$ this bound is correct up to a multiplicative constant.

Question 4: For $n \geq 1$ and $1 \leq m \leq n!$, let $\ell(m,n)$ be the least integer such that ${\ell(m,n) \choose n} \geq m$. Is there a positive constant $C$ such that $h(n,m) \leq C\ell(m,n)$?

[A] L. Adleman, Short permutation strings, Discrete Mathmatics, 1974.
[KK] D. Kleitman and D. Kwiatkowsky, A lower bound on the length of a sequence containing all permutations as subsequences, Journal of Combinatorial Theory Series A, 1976.
[S] C. Savage, Short strings containing all $k$-element permutations, Discrete Mathematics, 1982.
[Z] E. Zălinescu, Shorter strings containing all $k$-element permutations, Information Processing Letters, 2011.