Superpatterns and Generalizations of Layered Permutations

<div class="line" id="line-15"> In the study of permutation patterns, superpatterns are permutations that contain many patterns at least once. For a set P of permutations, we say that a permutation &sigma; is a P -superpattern if it contains every permutation in P , and we denote by sp(P ) the shortest length of all P -superpatterns. When P is the set of layered permutations of length k, it has been shown that sp(P ) = &Theta;(k log(k)). The notion of superpatterns can be extended naturally to words. In this talk, we explore some generalizations of layered permutations to &lsquo;layered words&rsquo; and seek to &filig;nd shortest lengths for superpatterns containing these sets.</div>