Some Results on Superpatterns for Preferential Arrangements
Document Type
Article
Publication Date
10-1-2016
Description
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.
Citation Information
Biers-Ariel, Yonah; Zhang, Yiguang; and Godbole, Anant. 2016. Some Results on Superpatterns for Preferential Arrangements. Advances in Applied Mathematics. Vol.81 202-211. https://doi.org/10.1016/j.aam.2016.08.004 ISSN: 0196-8858