Title

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.

Share

COinS