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

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 kap...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-03
Main Authors: Taylor, Allison, Godbole, Anant, Hawley, Kathryn, Kay, Bill
Format: Article
Language:English
Subjects:
Permutations
Phase transitions
Upper bounds
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422