Shortest supersequence of all permutations of $n$ elements

Question

Given an alphabet with $n$ characters, what is the shortest sequence that contains all $n!$ permutations as subsequences?

A subsequence can be obtained from a sequence by deleting any characters, thus it's different from a substring, whose elements have to be contiguous in the original sequence. I say this because the similar problem of finding the shortest sequence having all permutations as substrings seems to be more studied, but it's different from what I'm asking here.

Some examples of shortest supersequences:

• $n=2\quad-\quad121$ (length 3)
• $n=3\quad-\quad1213121$ (length 7)
• $n=4\quad-\quad1234123142134$ (length 13 - not proven to be shortest).

It's easy to see that $n^2$ is an upper bound, since a sequence $$12\ldots n\, 12\ldots n\, \ldots\, 12\ldots n $$ ($n$ times) contains all permutations. A simple lower bound is $n(n+1)/2$, basically because $$12\ldots n\; 12\ldots (n-1)\; 12\ldots (n-2)\;\ldots $$ is too short (this can be proven rigorously). Is anything more known about this problem?

The question was asked on stack exchange, but the answer there is far from satisfactory since it gives only a broken link and no reference.

Answer 1

This seems to be an open problem. It is listed in the OEIS as sequence A062714, as noted by Ilya. Summarising the most important results:

Let $m$ be the length of such a sequence. Then Newey (amongst others) describes a simple algorithm to generate them with $$m = n^2 -2n +4.$$ This is not, however, the best one. Radomirovic proves that the shortest sequences obey the tighter upper bound of $$m \le \left\lceil n^2 - \frac73 n + \frac{19}3\right\rceil.$$ A lower bound better than the trivial one shown by OP is given by Kleitman and Kwiatkowski: $$m \ge n^2 - C_\epsilon n^{7/4+\epsilon},$$ for any $\epsilon > 0$.

Answer 2

This is a suggestion for further development, as opposed to an answer. It seems to hold much promise.

Note that the n^2 upper bound can easily be shortened by 2, since any permutation not beginning with 1 and not ending in n does not need those letters in the example, and otherwise encodes a shorter permutation which does not need the first n or last n letters of the example.

More generally, the only permutation that "needs" all n^2 letters is the permutation with all descending letters: if a_i less than a_{i+1} then put those in the ith run, and now you can make do with one less run of letters. I believe you can extend this to chop off n-1 letters from either end when n is sufficiently large.

Even more generally, replace one of the middle runs 1...n with a shorter decreasing run n-1...2: if now there is a decrease of three or more consecutive elements, the longest or perhaps the "most central" such falling run can be placed in the middle, and the rest of the permutation on either side.

I believe a careful analysis of up down sequences in permutations will show a nice upper bound of n(n - sqrt(n)) using an example of sqrt(n) falling runs interspersed with n- 2sqrt(n) rising runs.