2016/03/05 by Yonah Biers-Ariel, Biers-Ariel, Yonah, Yiguang Zhang +3 · 1 citation
Mathematics · #05D99 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D99
paper · pdf · doi:10.48550/arxiv.1603.01736
13 pages
arxiv created 2016/03/05 · arxiv updated 2016/03/08
A \it 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 \em 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.