Covering \(n\)-permutations with \((n+1)\)-permutations (Q1953379): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 17:24, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Covering \(n\)-permutations with \((n+1)\)-permutations |
scientific article |
Statements
Covering \(n\)-permutations with \((n+1)\)-permutations (English)
0 references
7 June 2013
0 references
Summary: 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 \({\mathcal 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 \({\mathcal 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.
0 references
probability of coverage
0 references