### Covering n-Permutations with (n+1)-Permutations

#### Abstract

Let $S_n$ be the set of all permutations on $[n]:=\{1,2,\ldots,n\}$. We denote by $\kappa_n$ the smallest cardinality of a subset ${\cal A}$ of $S_{n+1}$ that "covers" $S_n$, in the sense that each $\pi\in S_n$ may be found as an order-isomorphic subsequence of some $\pi'$ in ${\cal A}$. What are general upper bounds on $\kappa_n$? If we randomly select $\nu_n$ elements of $S_{n+1}$, when does the probability that they cover $S_n$ transition from 0 to 1? Can we provide a fine-magnification analysis that provides the "probability of coverage" when $\nu_n$ is around the level given by the phase transition? In this paper we answer these questions and raise others.