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 ${\cal 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 ${\cal 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.
@article{10_37236_2168,
author = {Taylor F Allison and Anant P Godbole and Kathryn M Hawley and Bill Kay},
title = {Covering \(n\)-permutations with \((n+1)\)-permutations},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2168},
zbl = {1267.05059},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2168/}
}
TY - JOUR
AU - Taylor F Allison
AU - Anant P Godbole
AU - Kathryn M Hawley
AU - Bill Kay
TI - Covering \(n\)-permutations with \((n+1)\)-permutations
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2168/
DO - 10.37236/2168
ID - 10_37236_2168
ER -
%0 Journal Article
%A Taylor F Allison
%A Anant P Godbole
%A Kathryn M Hawley
%A Bill Kay
%T Covering \(n\)-permutations with \((n+1)\)-permutations
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2168/
%R 10.37236/2168
%F 10_37236_2168
Taylor F Allison; Anant P Godbole; Kathryn M Hawley; Bill Kay. Covering \(n\)-permutations with \((n+1)\)-permutations. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2168
