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.

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.

Consider a sequence (Formula presented.) of i.i.d. uniform random variables taking values in the alphabet set {1, 2,…, d}. A k-superpattern is a realization of (Formula presented.) that contains, as an embedded subsequence, each of the non-order-isomorphic subpatterns of length k. We focus on the (non-trivial) case of d = k = 3 and study the waiting time distribution of (Formula presented.). Our restricted set-up leads to proofs that are very combinatorial in nature, since we are essentially conducting a string analysis.