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.