Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4624498 | Advances in Applied Mathematics | 2016 | 10 Pages |
Abstract
A superpattern is a string of characters of length n over [k]={1,2,…,k}[k]={1,2,…,k} that contains as a subsequence, and in a sense that depends on the context, all the smaller strings of length k in a certain class. We prove structural and probabilistic results on superpatterns for preferential arrangements , including (i) a theorem that demonstrates that a string is a superpattern for all preferential arrangements if and only if it is a superpattern for all permutations; and (ii) a result that is reminiscent of a still unresolved conjecture of Alon on the smallest permutation on [n][n] that contains all k-permutations with high probability.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Yonah Biers-Ariel, Yiguang Zhang, Anant Godbole,