<p>Proposition 4.1 of <a href="https://arxiv.org/abs/2004.02375" rel="nofollow noreferrer">https://arxiv.org/abs/2004.02375</a> states that for sufficiently large <span class="math-container">$n$</span>, if <span class="math-container">$s$</span> has length less than <span class="math-container">$(1+e^{-600})n^2/e$</span> then <span class="math-container">$\#_n(s)\le \exp(e^{-600}n)n!$</span>. (note that here they respectively use <span class="math-container">$k,n$</span> in place of <span class="math-container">$n,c_n$</span>)</p>
<p>Thus even if <span class="math-container">$c_n$</span> grows quadratically but with a small constant, any <span class="math-container">$s$</span> with length <span class="math-container">$c_n$</span> will have an exponentially small proportion of permutations on <span class="math-container">$[n]$</span> as subsequences.</p>
<p>A more crude bound is that <span class="math-container">$s$</span> has length <span class="math-container">$c_n$</span>, then it contains at most <span class="math-container">$(c_n/n)^n$</span> different subsequences with each letter in <span class="math-container">$[n]$</span> appearing once (this can be seen by convexity, the number of (not necessarily unique) subsequences is <span class="math-container">$a_1a_2\dots a_n$</span> where <span class="math-container">$a_i$</span> counts the number of appearances of <span class="math-container">$i$</span> in <span class="math-container">$s$</span>, and this product is optimized by having <span class="math-container">$a_1 = \dots = a_n = c_n/n$</span>).</p>

CC BY-SA 4.0
2021-08-25T20:10:06.310Z
2021-08-25T20:31:51.923Z
2021-08-25T20:31:51.923Z
Zach Hunter
<p>A shortest supersequence $c_n$ of all permutations on $[n]$ has length $\Theta(n^2)$: <a href="https://mathoverflow.net/q/165303/840">see this question on Mathoverflow</a>. What if we force $c_n$ to be short? How many permutations can it cover?</p>

<p>Let's define $\#_n(s)$ to be the number of permutations on $[n]$ that are subsequences of $s$. Let $C$ denote an algorithm that reads an integer $n$ and produces a sequence of integers from $[n]$, and has a runtime bounded by $O(n\cdot{\rm polylog}(n))$. The function $f_C(n)=\#_n C(n)$ says how good algorithm $C$ is. Let $f = \sup_C f_C$, with functions ordered by their asymptotic behavior. What is the asymptotic behavior of $f$?</p>

<p>Has this or a similar problem been studied?</p>

<co.combinatorics>
Short supersequence for many permutations
Radu GRIGore
# Short supersequence for many permutations

(Asked by: username_0 on 2017-08-02)

A shortest supersequence $c\_n$ of all permutations on $[n]$ has length $\Theta(n^2)$: [see this question on Mathoverflow](https://mathoverflow.net/q/165303/840). What if we force $c\_n$ to be short? How many permutations can it cover?

Let's define $\#\_n(s)$ to be the number of permutations on $[n]$ that are subsequences of $s$. Let $C$ denote an algorithm that reads an integer $n$ and produces a sequence of integers from $[n]$, and has a runtime bounded by $O(n\cdot{\rm polylog}(n))$. The function $f\_C(n)=\#\_n C(n)$ says how good algorithm $C$ is. Let $f = \sup\_C f\_C$, with functions ordered by their asymptotic behavior. What is the asymptotic behavior of $f$?

Has this or a similar problem been studied?

**Tags:** co.combinatorics

---

## 1 answers

### Answer by username_1 on 2021-08-25. Score: 3

Proposition 4.1 of <https://arxiv.org/abs/2004.02375> states that for sufficiently large $n$, if $s$ has length less than $(1+e^{-600})n^2/e$ then $\#\_n(s)\le \exp(e^{-600}n)n!$. (note that here they respectively use $k,n$ in place of $n,c\_n$)

Thus even if $c\_n$ grows quadratically but with a small constant, any $s$ with length $c\_n$ will have an exponentially small proportion of permutations on $[n]$ as subsequences.

A more crude bound is that $s$ has length $c\_n$, then it contains at most $(c\_n/n)^n$ different subsequences with each letter in $[n]$ appearing once (this can be seen by convexity, the number of (not necessarily unique) subsequences is $a\_1a\_2\dots a\_n$ where $a\_i$ counts the number of appearances of $i$ in $s$, and this product is optimized by having $a\_1 = \dots = a\_n = c\_n/n$).


---

