2
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – igel
    Aug 1 at 16:48
  • 1
    $\begingroup$ 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). $\endgroup$ Aug 1 at 20:23
  • $\begingroup$ 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? $\endgroup$
    – igel
    Aug 2 at 8:33
  • 1
    $\begingroup$ yes, but we have that $(e^2/10^2)^L=o(1)$. this gets the job done! $\endgroup$ Aug 2 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.