# Superpattern
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Superpattern
> Markdown URL: https://mediated.wiki/source/Superpattern.md
> Source: https://en.wikipedia.org/wiki/Superpattern
> Source revision: 1335741295
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
In the mathematical study of [permutation](/source/permutation)s and [permutation pattern](/source/permutation_pattern)s, 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''.[{{citation|title=Combinatorics of Permutations|volume=72|series=Discrete Mathematics and Its Applications|first=Miklós|last=Bóna| author-link = Miklós Bóna | edition=2nd|publisher=CRC Press|year=2012|page=227|url=https://books.google.com/books?id=Op-nF-mBR7YC&pg=PA227|isbn=9781439850510}}.]
==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''1, ''s''2, ..., ''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](/source/Order_isomorphism) to the subsequence. For instance, if π is the permutation 25314, then it has ten subsequences of length three, forming the following patterns:
{| class="wikitable"
|-
! 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==
{{harvs|last=Arratia|authorlink=Richard Arratia|year=1999|txt}} 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](/source/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
}}] He observed that there exists a superpattern of length ''k''2 (given by the [lexicographic ordering](/source/lexicographic_ordering) on the coordinate vectors of points in a square grid) 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](/source/Stirling's_approximation) that ''n'' ≥ ''k''2/''e''2, where ''e'' ≈ 2.71828 is [Euler's number](/source/e_(mathematical_constant)).
This lower bound was later improved very slightly by
{{harvs|last1=Chroman|last2=Kwan|last3=Singhal|year=2021|txt}},
who increased it to 1.000076''k''2/''e''2,[{{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](/source/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
}}] disproving [Arratia](/source/Richard_Arratia)'s conjecture that the ''k''2/''e''2 lower bound was tight.[{{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](/source/Annals_of_Combinatorics)
| mr = 2376116
| pages = 459–470
| title = Dense packing of patterns in a permutation
| volume = 11
| year = 2007| s2cid = 2021533
}}]
{{harvs|last=Miller|authorlink=Alison Miller|year=2009|txt}} 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](/source/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
{{harvs|last1=Engen|last2=Vatter|year=2021|txt}}, who lowered it to ⌈(''k''2 + 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](/source/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 ''k''2/2.[{{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}}] {{harvtxt|Arratia|1999}} observes that, because the [longest increasing subsequence](/source/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 ''k''2/4 to have high probability of being a ''k''-superpattern: permutations shorter than this will likely not contain the identity pattern.