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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-16381 |
| Date | 01 October 2016 |
| Creators | Biers-Ariel, Yonah, Zhang, Yiguang, Godbole, Anant |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0153 seconds