Covering \(n\)-permutations with \((n+1)\)-permutations (Q1953379): Difference between revisions

Summary: 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 \({\mathcal 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 \({\mathcal 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.