Shortest Common Supersequence of Permutations

Question

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.

Answer 1

There should exist some absolute constant $C$ such that, the following lower bound holds: $$q_k(n) \ge kn-(C+o(1))k^2 \sqrt{n}, $$ which is much stronger than your conjecture.

The idea is this:

If you take two random permutations $\pi_1,\pi_2$ of length $n$, then the probability that they share a “common subsequence” of length $>10\sqrt{n}$ is $o(1)$ (this is a basic first moment exercise about ‘longest increasing subsequences’, since WLOG the problem does not change if we assume $\pi_1$ is the increasing permutation). Consequently, if $n$ is big enough with respect to $k$, then if we randomly choose $k$ permutations of length $n$, then with positive probability no pair of distinct permutations will have a common subsequence of length $>10\sqrt{n}$ (this is seen by taking a union bound, since we want to avoid $\binom{k}{2}=O_k(1)$ events that each happen with probability $o(1)$).

Fix such a choice of $k$ permutations, $\pi_1,\dots,\pi_k$, and suppose $s$ was a supersequence of them, having length $\ell$. Let $I_1,\dots,I_k \subset \{1,\dots,\ell\}$ be a choice of indices such that the $s|_{I_j}= \pi_j$ for each $j$. By construction, this implies that $|I_j \cap I_{j’}| \le 10 \sqrt{n}$ for all distinct $j,j’$. We are then done by noting that this implies $$\ell \ge \sum_{j=1}^k |I_j| -\sum_{j’<j} |I_j\cap I_{j’}| \ge kn - \binom{k}{2}10\sqrt{n}.$$