For integers $k$ and $n$, let $P_{k,n}$ be the set of all size-$k$ sets of permutations of $[n]$.
The Shortest Common Supersequence for Permutations (SCSP) problem is:
given a set $S\in P_{k,n}$, return a shortest string $s$ over the alphabet $[n]$ such that each $s_i\in S$ can be obtained by removing symbols from $s$.
Now, I am interested in the function family $q_k:\mathbb{N}\to\mathbb{N}$ with $q_k(n):=\max\{|SCSP(S)| \mid S\in P_{k,n} \}$, that is, given $n$, the function $q_k$ returns the smallest integer $\ell$ such that each $S\in P_{k,n}$ has a length-$\ell$ supersequence (note that this is not necessarily the same supersequence for each such set $S$).
It is fairly obvious that $n \leq q_k(n) \leq k\cdot n$, but I'm interested in less trivial bounds for this function. In particular, I would like to conjecture that $(k-\frac{1}{k-1})\cdot n - o(1)\leq q_k(n)$. Is anything known regarding these bounds?
Related Questions
The special case of $k=n!$, that is, supersequences containing all permutations of $[n]$, has been discussed on mathoverflow, where $q_{n!}(n)\in \Theta(n^2)$ is indicated. However, this shouldn't have any bearing on the asymptotics of any $q_k$ for fixed $k\in\mathbb{N}$. In particular, this doesn't contradict my conjecture above because of the $o(1)$ term that may depend on $k$.
A related question here on cstheory asked (I think) for a similar function $f_\ell$ mapping each $n\in\mathbb{N}$ to the largest number $k\in\mathbb{N}$ with $\ell \geq \min\{|SCSP(S)| \mid S\in P_{k,n} \}$. In simpler terms, $f_\ell$ maps each $n$ to the maximum number of permutations of $[n]$ that have a length-$\ell$ supersequence.