Miklos Bona:


Superpatterns and Superpermutations


At least how long does a permutation have to be if it is to contain all patterns of length $k$? At least how long does a word over the alphabet $\{1,2,\cdots ,n\}$ have to be if it is to contain all permutations as a subsequence. As a factor? These questions are easy to formulate, but surprisingly difficult to answer, even at the level of bounds. It is quite possible that for some of these questions, the best answers will come from constructions of geometric nature. No previous knowledge of the combinatorics of permutations or pattern avoidance will be assumed.