Covering n-Permutations With (n + 1)-Permutations
Document Type
Article
Publication Date
1-14-2013
Description
Let Sn be the set of all permutations on [n]:= {1, 2,..., n}. We denote by κn the smallest cardinality of a subset A of Sn+1 that covers Sn, in the sense that each π ∈ Sn may be found as an order-isomorphic subsequence of some π′ in A. What are general upper bounds on κn? If we randomly select νn elements of Sn+1, when does the probability that they cover Sn transition from 0 to 1? Can we provide a fine-magnification analysis that provides the "probability of coverage" when νn is around the level given by the phase transition? In this paper we answer these questions and raise others.
Citation Information
Allison, Taylor F.; Hawley, Kathryn M.; Godbole, Anant P.; and Kay, Bill. 2013. Covering n-Permutations With (n + 1)-Permutations. Electronic Journal of Combinatorics. Vol.20(1). https://doi.org/10.37236/2168