×

Covering \(n\)-permutations with \((n+1)\)-permutations. (English) Zbl 1267.05059

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
PDFBibTeX XMLCite
Full Text: arXiv Link