Superpattern
title: "Superpattern" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["permutation-patterns"] topic_path: "general/permutation-patterns" source: "https://en.wikipedia.org/wiki/Superpattern" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
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 = s1, s2, ..., 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:
::data[format=table]
| 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.{{citation | last = Arratia | first = Richard | author-link = Richard Arratia | journal = Electronic Journal of Combinatorics | mr = 1710623 | article-number = N1 | title = On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern | url = http://www.combinatorics.org/Volume_6/Abstracts/v6i1n1.html | volume = 6 | year = 1999| doi = 10.37236/1477 | doi-access = free This lower bound was later improved very slightly by , who increased it to 1.000076k2/e2,{{citation | last1 = Chroman | first1 = Zachary | last2 = Kwan | first2 = Matthew | last3 = Singhal | first3 = Mihir | arxiv = 2004.02375 | doi = 10.1016/j.jcta.2021.105467 | journal = Journal of Combinatorial Theory | mr = 4253319 | at = Paper No. 105467 (15 pp) | series = Series A | title = Lower bounds for superpatterns and universal sequences | volume = 182 | year = 2021 | article-number = 105467
The upper bound of k2 on superpattern length proven by Arratia is not tight. After intermediate improvements,{{citation | last1 = Eriksson | first1 = Henrik | last2 = Eriksson | first2 = Kimmo | last3 = Linusson | first3 = Svante | last4 = Wästlund | first4 = Johan | doi = 10.1007/s00026-007-0329-7 | issue = 3–4 | journal = Annals of Combinatorics | mr = 2376116 | pages = 459–470 | title = Dense packing of patterns in a permutation | volume = 11 | year = 2007| s2cid = 2021533 proved that there is a k-superpattern of length at most k(k + 1)/2 for every k.{{citation | last = Miller | first = Alison | author-link = Alison Miller | doi = 10.1016/j.jcta.2008.04.007 | issue = 1 | journal = Journal of Combinatorial Theory | pages = 92–108 | series = Series A | title = Asymptotic bounds for permutations containing many different patterns | volume = 116 | year = 2009| doi-access = This bound was later improved by , who lowered it to ⌈(k2 + 1)/2⌉.{{citation | last1 = Engen | first1 = Michael | last2 = Vatter | first2 = Vincent | title = Containing all permutations | doi = 10.1080/00029890.2021.1835384 | doi-access = free | journal = American Mathematical Monthly | year = 2021 | volume = 128 | issue = 1 | pages = 4–24 | arxiv = 1810.08252
Eriksson et al. conjectured that the true length of the shortest k-superpattern is asymptotic to k2/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.{{citation | last1 = Godbole | first1 = Anant P. | last2 = Liendo | first2 = Martha | arxiv = 1302.4668 | doi = 10.1007/s11009-015-9439-6 | issue = 2 | journal = Methodology and Computing in Applied Probability | mr = 3488590 | pages = 517–528 | title = Waiting time distribution for the emergence of superpatterns | volume = 18 | year = 2016}} observes that, because the longest increasing subsequence of a random permutation has length (with high probability) approximately 2√n, it follows that a random permutation must have length at least k2/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 ε 0, with high probability, random permutations of length k2/(4 − ε) will be k-superpatterns.
References
References
- Bóna, Miklós. (2012). "Combinatorics of Permutations". CRC Press.
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::