Short supersequence for many permutations

Question

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?

Answer 1

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