# Shortest Common Supersequence of Permutations

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.

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’

• Cool, this sounds right, thanks for the answer. I just have difficulties with the "basic first moment exercise". I understand that it's equivalent to estimate the probability of a random permutation having an increasing subsequence of length $>10\sqrt{n}$, but I don't quite get why this is in $o(1)$. Apologies for my lack of statistics.
– igel
Aug 1 at 16:48
• Here’s the reason: write $L := 10 \sqrt{n}$. There are at most $\binom{n}{L} \le (en/L)^{L}$ possible sets of indices where a long LIS could occur. Each of these happen with probability $< 1/L! < (e/L)^{L}$ (by Stirling approximation). We then win since $e^2 n/L^2<1$ (meaning we can do a union bound). Aug 1 at 20:23
• This is also what I concluded, but $e^2n/L^2 = e^2/10^2$ is not in $o(1)$ since the limit with $n\to\infty$ goes to $e^2/10^2>0$, no?
– igel
Aug 2 at 8:33
• yes, but we have that $(e^2/10^2)^L=o(1)$. this gets the job done! Aug 2 at 12:00