A shortest supersequence $c_n$ of all permutations on $[n]$ has length $\Theta(n^2)$: see this question on Mathoverflow. What if we force $c_n$ to be short? How many permutations can it cover?

Let's define $\#_n(s)$ to be the number of permutations on $[n]$ that are subsequences of $s$. Let $C$ denote an algorithm that reads an integer $n$ and produces a sequence of integers from $[n]$, and has a runtime bounded by $O(n\cdot{\rm polylog}(n))$. The function $f_C(n)=\#_n C(n)$ says how good algorithm $C$ is. Let $f = \sup_C f_C$, with functions ordered by their asymptotic behavior. What is the asymptotic behavior of $f$?

Has this or a similar problem been studied?


Proposition 4.1 of https://arxiv.org/abs/2004.02375 states that for sufficiently large $n$, if $s$ has length less than $(1+e^{-600})n^2/e$ then $\#_n(s)\le \exp(e^{-600}n)n!$. (note that here they respectively use $k,n$ in place of $n,c_n$)

Thus even if $c_n$ grows quadratically but with a small constant, any $s$ with length $c_n$ will have an exponentially small proportion of permutations on $[n]$ as subsequences.

A more crude bound is that $s$ has length $c_n$, then it contains at most $(c_n/n)^n$ different subsequences with each letter in $[n]$ appearing once (this can be seen by convexity, the number of (not necessarily unique) subsequences is $a_1a_2\dots a_n$ where $a_i$ counts the number of appearances of $i$ in $s$, and this product is optimized by having $a_1 = \dots = a_n = c_n/n$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.