<p>There should exist some absolute constant <span class="math-container">$C$</span> such that, the following lower bound holds: <span class="math-container">$$q_k(n) \ge kn-(C+o(1))k^2 \sqrt{n}, $$</span> which is much stronger than your conjecture.</p>
<p>The idea is this:</p>
<p>If you take two random permutations <span class="math-container">$\pi_1,\pi_2$</span> of length <span class="math-container">$n$</span>, then the probability that they share a “common subsequence” of length <span class="math-container">$&gt;10\sqrt{n}$</span> is <span class="math-container">$o(1)$</span> (this is a basic first moment exercise about ‘longest increasing subsequences’, since WLOG the problem does not change if we assume <span class="math-container">$\pi_1$</span> is the increasing permutation). Consequently, if <span class="math-container">$n$</span> is big enough with respect to <span class="math-container">$k$</span>, then if we randomly choose <span class="math-container">$k$</span> permutations of length <span class="math-container">$n$</span>, then with positive probability no pair of distinct permutations will have a common subsequence of length <span class="math-container">$&gt;10\sqrt{n}$</span> (this is seen by taking a union bound, since we want to avoid <span class="math-container">$\binom{k}{2}=O_k(1)$</span> events that each happen with probability <span class="math-container">$o(1)$</span>).</p>
<p>Fix such a choice of <span class="math-container">$k$</span> permutations, <span class="math-container">$\pi_1,\dots,\pi_k$</span>, and suppose <span class="math-container">$s$</span> was a supersequence of them, having length <span class="math-container">$\ell$</span>. Let <span class="math-container">$I_1,\dots,I_k \subset \{1,\dots,\ell\}$</span> be a choice of indices such that the <span class="math-container">$s|_{I_j}= \pi_j$</span> for each <span class="math-container">$j$</span>. By construction, this implies that <span class="math-container">$|I_j \cap I_{j’}| \le 10 \sqrt{n}$</span> for all distinct <span class="math-container">$j,j’$</span>. We are then done by noting that this implies <span class="math-container">$$\ell \ge \sum_{j=1}^k |I_j| -\sum_{j’&lt;j} |I_j\cap I_{j’}| \ge kn - \binom{k}{2}10\sqrt{n}.$$</span></p>

CC BY-SA 4.0
2023-08-01T16:48:02.067Z
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
CC BY-SA 4.0
2023-08-01T20:23:03.530Z
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).
Zach Hunter
CC BY-SA 4.0
2023-08-02T08:33:36.653Z
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
CC BY-SA 4.0
2023-08-02T12:00:47.380Z
yes, but we have that $(e^2/10^2)^L=o(1)$. this gets the job done!
Zach Hunter
CC BY-SA 4.0
2023-07-31T20:22:04.487Z
2023-08-07T08:42:34.817Z
2023-08-07T08:42:34.817Z
Zach Hunter
<p>For integers <span class="math-container">$k$</span> and <span class="math-container">$n$</span>, let <span class="math-container">$P_{k,n}$</span> be the set of all size-<span class="math-container">$k$</span> sets of permutations of <span class="math-container">$[n]$</span>.</p>
<p>The Shortest Common Supersequence for Permutations (SCSP) problem is:</p>
<blockquote>
<p>given a set <span class="math-container">$S\in P_{k,n}$</span>, return a shortest string <span class="math-container">$s$</span> over the
alphabet <span class="math-container">$[n]$</span> such that each <span class="math-container">$s_i\in S$</span> can be obtained by removing
symbols from <span class="math-container">$s$</span>.</p>
</blockquote>
<p>Now, I am interested in the function family <span class="math-container">$q_k:\mathbb{N}\to\mathbb{N}$</span> with <span class="math-container">$q_k(n):=\max\{|SCSP(S)| \mid S\in P_{k,n} \}$</span>, that is, given <span class="math-container">$n$</span>, the function <span class="math-container">$q_k$</span> returns the smallest integer <span class="math-container">$\ell$</span> such that each <span class="math-container">$S\in P_{k,n}$</span> has a length-<span class="math-container">$\ell$</span> supersequence (note that this is not necessarily the same supersequence for each such set <span class="math-container">$S$</span>).</p>
<p>It is fairly obvious that <span class="math-container">$n \leq q_k(n) \leq k\cdot n$</span>, but I'm interested in less trivial bounds for this function. In particular, I would like to conjecture that <span class="math-container">$(k-\frac{1}{k-1})\cdot n - o(1)\leq q_k(n)$</span>. Is anything known regarding these bounds?</p>
<p><strong>Related Questions</strong></p>
<p>The special case of <span class="math-container">$k=n!$</span>, that is, supersequences containing <strong>all</strong> permutations of <span class="math-container">$[n]$</span>, has been discussed <a href="https://mathoverflow.net/questions/165303/shortest-supersequence-of-all-permutations-of-n-elements">on mathoverflow</a>, where <span class="math-container">$q_{n!}(n)\in \Theta(n^2)$</span> is indicated. However, this shouldn't have any bearing on the asymptotics of any <span class="math-container">$q_k$</span> for fixed <span class="math-container">$k\in\mathbb{N}$</span>. In particular, this doesn't contradict my conjecture above because of the <span class="math-container">$o(1)$</span> term that may depend on <span class="math-container">$k$</span>.</p>
<p>A related question <a href="https://cstheory.stackexchange.com/questions/38732/short-supersequence-for-many-permutations">here on cstheory</a> asked (I think) for a similar function <span class="math-container">$f_\ell$</span> mapping each <span class="math-container">$n\in\mathbb{N}$</span> to the largest number <span class="math-container">$k\in\mathbb{N}$</span> with <span class="math-container">$\ell \geq \min\{|SCSP(S)| \mid S\in P_{k,n} \}$</span>. In simpler terms, <span class="math-container">$f_\ell$</span> maps each <span class="math-container">$n$</span> to the maximum number of permutations of <span class="math-container">$[n]$</span> that have a length-<span class="math-container">$\ell$</span> supersequence.</p>

<co.combinatorics><permutations><asymptotics>
Shortest Common Supersequence of Permutations
igel
# Shortest Common Supersequence of Permutations

(Asked by: username_0 on 2023-07-31)

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](https://mathoverflow.net/questions/165303/shortest-supersequence-of-all-permutations-of-n-elements), 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](https://cstheory.stackexchange.com/questions/38732/short-supersequence-for-many-permutations) 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.

**Tags:** co.combinatorics, permutations, asymptotics

---

## 1 answers

### Answer by username_1 on 2023-07-31. Score: 4 | Accepted answer

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’

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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).  
> **username_0**: 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?  
> **username_1**: yes, but we have that $(e^2/10^2)^L=o(1)$. this gets the job done!  

---

