Superpattern

From Wikipedia, the free encyclopedia

A k-superpattern is a smallest combinatorial pattern that contains all k-subpatterns.

Contents

[edit] Definitions

A combinatorial pattern is a permutation of numbers from 1 to n, where n is some natural number. n is the length of the combinatorial pattern. A k-subpattern is a subset of size k of the original pattern with the order preserved but the pattern renumbered with respect to the sizes of its members.

[edit] Examples

Consider the combinatorial pattern 25314, which has length 5.

Now, consider some 3-subpatterns, which we take from 25314: 253, 251, 254, 234, 531, 534, 314 (we take 3 digits at a time, keeping the order preserved). We then renumber the selected subpatterns using the digits from 1 to 3 (since this is a 3-subpattern). In each subpattern, the smallest digit is replaced with a 1, the next larger one with a 2, and the largest with a 3. Thus, 253 gets renumbered to 132, 251 to 231, and so on. We end up with 132, 231, 123, 321, 312, 213. We could have picked 514, for example, for our original list of 3-subpatterns, but that would have just got renumbered to 312, which is a repetition of one of the subpatterns already picked. In fact, in our original list, we have selected all the possible 3-subpatterns, i.e. all 6 (3!) permutations of length 3.

From this, we can see that 25314 contains all possible 3-subpatterns. But, for it to be a 3-superpattern, it must be the smallest such combinatorial pattern.

Then, consider also that in order to have 123 and 321 in the same permutation, by the inclusion-exclusion principle we need a minimium of : 3 + 3 - 1 = 5 numbers (since only one number can be in both the largest increasing sequence and the largest decreasing sequence). This implies that any larger pattern which contains both 123 and 321 as substrings must be at least 5 digits long. 25314 is such a pattern and is therefore a 3-superpattern of length 5.

[edit] Theorems

k2/e<length(k-superpattern)<3k2/4.
The only lower bound proven for length(k-superpattern) is k2/e , which is proven by assuming that { n \choose k } \ge k! and applying Stirling's approximation to the binomial coefficient.
An upper bound on the length of a superpattern is length(k-superpattern)< 3k2/4, which is proven by showing the probability of finding a length(k-superpattern) in a 3k2/4-pattern is greater than 0.
It is believed that the length of k-superpatterns is approaching k2/2.

[edit] References