# Short supersequence for many permutations

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$$).