Allison, Taylor F.; Godbole, Anant P.; Hawley, Kathryn M.; Kay, Bill Covering \(n\)-permutations with \((n+1)\)-permutations. (English) Zbl 1267.05059 Electron. J. Comb. 20, No. 1, Research Paper P6, 13 p. (2013). 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. MSC: 05B40 Combinatorial aspects of packing and covering 05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) 05A05 Permutations, words, matrices Keywords:probability of coverage PDFBibTeX XMLCite \textit{T. F. Allison} et al., Electron. J. Comb. 20, No. 1, Research Paper P6, 13 p. (2013; Zbl 1267.05059) Full Text: arXiv Link