Superpattern

In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a k-superpattern contains all possible patterns of length k.

Definitions and example

If π is a permutation of length n, represented as a sequence of the numbers from 1 to n in some order, and s = s₁, s₂,..., s_k is a subsequence of π of length k, then s corresponds to a unique pattern, a permutation of length k whose elements are in the same order as s. That is, for each pair i and j of indexes, the i-th element of the pattern for s should be less than the j-th element if and only if the i-th element of s is less than the j-th element. Equivalently, the pattern is order-isomorphic to the subsequence. For instance, if π is the permutation 25314, then it has ten subsequences of length three, forming the following patterns:

Subsequence	Pattern
253	132
251	231
254	132
231	231
234	123
214	213
531	321
534	312
514	312
314	213

A permutation π is called a k-superpattern if its patterns of length k include all of the length-k permutations. For instance, the length-3 patterns of 25314 include all six of the length-3 permutations, so 25314 is a 3-superpattern. No 3-superpattern can be shorter, because any two subsequences that form the two patterns 123 and 321 can only intersect in a single position, so five symbols are required just to cover these two patterns.

Length bounds

introduced the problem of determining the length of the shortest possible k-superpattern. He observed that there exists a superpattern of length k² and also observed that, for a superpattern of length n, it must be the case that it has at least as many subsequences as there are patterns. That is, it must be true that, from which it follows by Stirling's approximation that n ≥ k²/e², where e ≈ 2.71828 is Euler's number.
This lower bound was later improved very slightly by
,
who increased it to 1.000076k²/e², disproving Arratia's conjecture that the k²/e² lower bound was tight.
The upper bound of k² on superpattern length proven by Arratia is not tight. After intermediate improvements,
proved that there is a k-superpattern of length at most k/2 for every k.
This bound was later improved by
, who lowered it to ⌈/2⌉.
Eriksson et al. conjectured that the true length of the shortest k-superpattern is asymptotic to k²/2.
However, this is in contradiction with a conjecture of Alon on random superpatterns described below.

Random superpatterns

Researchers have also studied the length needed for a sequence generated by a random process to become a superpattern. observes that, because the longest increasing subsequence of a random permutation has length approximately 2√n, it follows that a random permutation must have length at least k²/4 to have high probability of being a k-superpattern: permutations shorter than this will likely not contain the identity pattern. He attributes to Alon the conjecture that, for any, with high probability, random permutations of length will be k-superpatterns.