Abstract | ||
---|---|---|
A superpattern is a string of characters of length n over 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 that contains all k-permutations with high probability.
|
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.aam.2016.08.004 | Advances in Applied Mathematics |
Keywords | Field | DocType |
05A05, 05D40, 05D99, Complete words, Permutation, Preferential arrangement, Superpattern | Discrete mathematics,Combinatorics,Permutation,If and only if,Probabilistic logic,Subsequence,Conjecture,Mathematics | Journal |
Volume | ISSN | Citations |
81 | 0196-8858 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yonah Biers-Ariel | 1 | 0 | 0.34 |
Yiguang Zhang | 2 | 0 | 0.68 |
Anant P. Godbole | 3 | 95 | 16.08 |