Covering n-Permutations with (n+1)-Permutations

Details Covering n-Permutations with (n+1)-Permutations Covering n-Permutations with (n+1)-Permutations

2012-03-24

arxiv.org/abs/1203.5433v1

Mathematics

Combinatorics

18 pages

Scientific paper

Let S_n be the set of all permutations on [n]:={1,2,....,n}. We denote by kappa_n the smallest cardinality of a subset 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 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.

Affiliated with

Also associated with

No associations

Rating

Covering n-Permutations with (n+1)-Permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Covering n-Permutations with (n+1)-Permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Covering n-Permutations with (n+1)-Permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-39214