Preferential Arrangement Superpatterns
Document Type
Article
Publication Date
10-1-2016
Description
A superpattern is a string of characters of length n 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; Godbole, Anant; and Zhang, Yiguang. 2016. Preferential Arrangement Superpatterns. Electronic Notes in Discrete Mathematics. Vol.54 9-14. https://doi.org/10.1016/j.endm.2016.09.003