Content deleted Content added
m →Generalizations: − |
|||
| (17 intermediate revisions by 9 users not shown) | |||
Line 1:
{{Short description|Subpermutation of a longer permutation}}
In [[combinatorics|combinatorial mathematics]] and [[theoretical computer science]], a (classical) '''permutation pattern''' is a sub-permutation of a longer [[permutation]]. Any permutation may be written in [[Permutation#One-line_notation|one-line notation]] as a sequence of entries representing the result of applying the permutation to the sequence 123...; for instance the sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way (these variable names are standard for permutations and are unrelated to the number [[pi]]), then π is said to ''contain'' σ as a ''pattern'' if some [[subsequence]] of the entries of π has the same relative order as all of the entries of σ.
Line 6 ⟶ 7:
If a permutation π does not contain a pattern σ, then π is said to ''avoid'' σ. The permutation 51342 avoids 213; it has ten subsequences of three entries, but none of these ten subsequences has the same ordering as 213.
An international conference dedicated to permutation patterns and related topics has been held annually since 2003, called ''[[Permutation Patterns (conference) | Permutation Patterns]]''.
== Early results ==
Line 51 ⟶ 54:
| doi=10.1016/s0195-6698(85)80052-4
| doi-access=free
}}.</ref> Since their paper, many other bijections have been given, see {{harvtxt|Claesson|Kitaev|2008}} for a survey.<ref>{{Citation| last1=Claesson | first1=Anders| last2=Kitaev | first2=Sergey| author2-link = Sergey Kitaev| arxiv = 0805.1325| title=Classification of bijections between 321- and 132-avoiding permutations| year=2008| journal=[[Séminaire Lotharingien de Combinatoire]]| url = https://www.mat.univie.ac.at/~slc/wpapers/s60claekit.html| volume=60| pages=B60d, 30pp
In general, if |Av''<sub>n</sub>''(''β'')| = |Av''<sub>n</sub>''(''σ'')| for all ''n'', then ''β'' and ''σ'' are said to be [[Wilf equivalence|''Wilf-equivalent'']]. Many Wilf-equivalences stem from the trivial fact that |Av''<sub>n</sub>''(''β'')| = |Av''<sub>n</sub>''(''β''<sup>−1</sup>)| = |Av''<sub>n</sub>''(''β''<sup>rev</sup>)| for all ''n'', where ''β''<sup>−1</sup> denotes the [[Permutation#Product and inverse|inverse]] of ''β'' and ''β''<sup>rev</sup> denotes the reverse of ''β''. (These two operations generate the [[Examples of groups#The symmetry group of a square - dihedral group of order 8|Dihedral group D<sub>8</sub>]] with a natural action on [[permutation matrices]].) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between
* {{harvtxt|Stankova|1994}} proved that the permutations 1342 and 2413 are Wilf-equivalent.<ref>{{Citation | last1=Stankova | first1=Zvezdelina | title=Forbidden subsequences | mr = 1297387 | year=1994 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]] | volume=132 | issue=1–3 | pages=291–316 | doi = 10.1016/0012-365X(94)90242-9| doi-access=free }}.</ref>
* {{harvtxt|Stankova|West|2002}} proved that for any permutation ''β'', the permutations 231 ⊕ ''β'' and 312 ⊕ ''β'' are Wilf-equivalent, where ⊕ denotes the [[direct sum of permutations|direct sum]] operation.<ref>{{Citation | last1=Stankova | first1=Zvezdelina | last2=West | first2=Julian | title=A New class of Wilf-Equivalent Permutations | mr = 1900628 | year=2002 | journal=[[Journal of Algebraic Combinatorics]] | volume=15 | issue=3 | pages=271–290 | doi = 10.1023/A:1015016625432| arxiv=math/0103152 | s2cid=13921676 }}.</ref>
* {{harvtxt|Backelin|West|Xin|2007}} proved that for any permutation ''β'' and any positive integer ''m'', the permutations 12...''m'' ⊕ ''β'' and ''m''...21 ⊕ ''β'' are Wilf-equivalent.<ref>{{citation | last1=Backelin | first1=Jörgen | last2=West | first2=Julian | last3=Xin | first3=Guoce | title=Wilf-equivalence for singleton classes
| mr = 2290807 | year=2007 | journal=[[Advances in Applied Mathematics]] | volume=38 | issue=2 | pages=133–149 | doi = 10.1016/j.aam.2004.11.006| doi-access=free }}.</ref>
Line 75 ⟶ 78:
In the late 1980s, [[Richard P. Stanley|Richard Stanley]] and [[Herbert Wilf]] conjectured that for every permutation ''β'', there is some constant ''K'' such that |Av''<sub>n</sub>''(''β'')| < ''K<sup>n</sup>''. This was known as the [[Stanley–Wilf conjecture]] until it was proved by [[Adam Marcus (mathematician)|Adam Marcus]] and [[Gábor Tardos]].<ref>{{Citation | last1=Marcus | first1=Adam | last2=Tardos | first2= Gábor | author2-link=Gábor Tardos | title=Excluded permutation matrices and the Stanley-Wilf conjecture | mr = 2063960 | year=2004 | journal=[[Journal of Combinatorial Theory]]|series=Series A | volume=107 | issue=1 | pages=153–160 | doi=10.1016/j.jcta.2004.04.002| doi-access=free }}.</ref>
==
{{main|Permutation class}}
A ''
== Möbius function ==
As the set of permutations under the containment order forms a [[Partially ordered set|poset]] it is natural to ask about its [[incidence algebra#Special elements|Möbius function]], a goal first explicitly presented by {{harvtxt|Wilf|2002}}.<ref>{{citation | last1=Wilf | first1=Herbert | authorlink = Herbert Wilf |title=Patterns of permutations | mr = 1935750 | year=2002 | journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]| volume=257 | issue=2 | pages=575–583 | doi = 10.1016/S0012-365X(02)00515-0| doi-access=free }}.</ref>
The goal in such investigations is to find a formula for the Möbius function of an interval [σ, π] in the permutation pattern poset which is more efficient than the naïve recursive definition. The first such result was established by {{harvtxt|Sagan|Vatter|2006}}, who gave a formula for the Möbius function of an interval of [[layered permutation]]s.<ref>{{Citation | last1=Sagan | first1=Bruce | author1-link=Bruce Sagan | last2=Vatter | first2= Vince | title=The Möbius function of a composition poset | mr = 2259013 | year=2006 | journal=[[Journal of Algebraic Combinatorics]] | volume=24 | issue=2 | pages=117–136 | doi=10.1007/s10801-006-0017-4| arxiv=math/0507485 | s2cid=11283347 }}.</ref>
Later, {{harvtxt|Burstein|Jelinek|Jelinkova|Steingrimsson|2011}} generalized this result to intervals of [[separable permutation]]s.<ref>{{Citation | last1=Burstein | first1=Alexander | last2=Jelinek | first2= Vit | last3=Jelinkova | first3=Eva | last4=Steingrimsson | first4= Einar |author4-link=Einar Steingrímsson|title=The Möbius function of separable and decomposable permutations | mr = 2834180 | year=2011 | journal=[[Journal of Combinatorial Theory]]|series=Series A | volume=118 | issue=1 | pages=2346–2364 | doi=10.1016/j.jcta.2011.06.002| s2cid=13978488 | doi-access=free }}.</ref>
It is known that, asymptotically, at least 39.95% of all permutations π of length ''n'' satisfy μ(1, π)=0 (that is, the principal Möbius function is equal to zero),<ref>{{citation |last1=Brignall |first1=Robert |last2=Jelínek |first2=Vit |last3=Kynčl |first3=Jan |last4=Marchant |first4=David |title=Zeros of the Möbius function of permutations | year=2019 | journal=[[Mathematika]] |volume=65 |issue=4 |pages=1074–1092 | mr=3992365 | doi=10.1112/S0025579319000251|s2cid=53366318 |url=http://oro.open.ac.uk/66369/1/181012-Marchant-v101.pdf |arxiv=1810.05449 }}</ref> but for each ''n'' there exist permutations π such that μ(1, π) is an exponential function of ''n''.<ref>{{citation |last1=Marchant |first1=David |title=2413-balloon permutations and the growth of the Möbius function |journal=[[Electronic Journal of Combinatorics]] |date=2020 |volume=27 |issue=1 |page=Article P1.7, 18 pp
== Computational complexity ==
Line 92 ⟶ 95:
There are several variants on the PPM problem, as surveyed by Bruner and Lackner.<ref>{{citation|title=The computational landscape of permutation patterns|first1=Marie-Louise|last1=Bruner|first2=Martin|last2=Lackner|year=2013|journal=Pure Mathematics and Applications|volume=24|issue=2|pages=83–101|arxiv=1301.0340}}</ref> For example, if the match is required to consist of contiguous entries then the problem can be solved in polynomial time.<ref>{{citation|last1=Kubica|first1=M.|last2=Kulczyński|first2=T.|last3=Radoszewski|first3=J.|last4=Rytter|first4=W.|last5=Waleń|first5=T.|title=A linear time algorithm for consecutive permutation pattern matching|journal=[[Information Processing Letters]]|year=2013|volume=113|issue=12|pages=430–433|doi=10.1016/j.ipl.2013.03.015}}</ref> A different natural variant is obtained when the pattern is restricted to a proper permutation class <math>\mathcal{C}</math>. This problem is known as <math>\mathcal{C}</math>-Pattern PPM and it was shown to be polynomial-time solvable for [[separable permutations]].<ref name="BBL 1998"/> Later, Jelínek and Kynčl<ref name="JK 2017">{{cite conference|title=Hardness of Permutation Pattern Matching|first1=Vít|last1=Jelínek|first2=Jan|last2=Kynčl|year=2017|book-title=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19|publisher=SIAM|pages=378–396|arxiv=1608.00529|doi=10.1137/1.9781611974782.24}}</ref> completely resolved the complexity of <math>\mbox{Av}(\sigma)</math>-Pattern PPM by showing that it is polynomial-time solvable when <math>\sigma</math> is equal to one of 1, 12, 21, 132, 231, 312 or 213 and NP-complete otherwise.
Another variant is when both the pattern and text are restricted to a proper permutation class <math>\mathcal{C}</math>, in which case the problem is called <math>\mathcal{C}</math>-PPM. For example, Guillemot and Vialette<ref>{{citation|last1=Guillemot|first1=Sylvain|last2=Vialette|first2=Stéphane|contribution=Pattern matching for 321-avoiding permutations|title=Algorithms and Computation|year=2009|volume=5878|series=Lecture Notes in Computer Science|pages=1064–1073|doi=10.1007/978-3-642-10631-6_107|arxiv=1511.01770|isbn=978-3-642-10630-9 }}</ref> showed that <math>\mbox{Av}(321)</math>-PPM could be solved in <math>O(k^2n^6)</math> time. [[Michael H. Albert|Albert]], Lackner, Lackner, and Vatter<ref>{{citation|last1=Albert|first1=Michael | author1-link=Michael H. Albert |last2=Lackner|first2=Marie-Louise|last3=Lackner|first3=Martin|last4=Vatter|first4=Vincent|year=2016|volume=18|issue=2|journal=Discrete Mathematics & Theoretical Computer Science|title=The complexity of pattern matching for 321-avoiding and skew-merged permutations|doi=10.46298/dmtcs.1308 |arxiv=1510.06051|s2cid=5827603 }}</ref> later lowered this to <math>O(kn)</math> and showed that the same bound holds for the class of [[skew-merged permutation]]s. They further asked if the <math>\mathcal{C}</math>-PPM problem can be solved in polynomial time for every fixed proper permutation class <math>\mathcal{C}</math>. This question was answered negatively by Jelínek and Kynčl who showed that <math>\mbox{Av}(4321)</math>-PPM is in fact NP-complete.<ref name="JK 2017" /> Later, Jelínek, Opler, and Pekárek<ref>{{cite conference|title=Griddings of Permutations and Hardness of Pattern Matching|first1=Vít|last1=Jelínek|first2=Michal|last2=Opler|first3=Jakub|last3=Pekárek|year=2021|book-title=46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia|publisher=Schloss Dagstuhl - Leibniz-Zentrum für Informatik|issue=2|pages=65:1–65:22|arxiv=2107.10897|doi=10.4230/LIPIcs.MFCS.2021.65|doi-access=free }}</ref> showed that <math>\mbox{Av}(\sigma)</math>-PPM is NP-complete for any <math>\sigma</math> of length at least 4 not symmetric to one of 3412, 3142, 4213, 4123 or 41352.
== Packing densities ==
Line 102 ⟶ 105:
</math>
An unpublished argument of [[Fred Galvin]] shows that the quantity inside this [[limit of a sequence|limit]] is nonincreasing for ''n'' ≥ ''k'', and so the limit exists. When β is monotone, its packing density is clearly 1, and packing densities are invariant under the group of symmetries generated by inverse and reverse, so for permutations of length three, there is only one nontrivial packing density. Walter Stromquist (unpublished) settled this case by showing that the packing density of 132 is {{math|2{{radic|3}} − 3}}, approximately 0.46410.
For permutations β of length four, there are (due to symmetries) seven cases to consider:
Line 112 ⟶ 115:
| 1234 || 1 || trivial
|-
| 1432 || root of {{math|''x''<sup>3</sup> − 12''x''<sup>2</sup> + 156''x'' − 64 ≅ 0.42357}} || {{harvtxt|Price|1997}}<ref name="price97">{{citation | last=Price | first=Alkes | title=Packing densities of layered patterns | publisher=University of Pennsylvania | series = Ph.D. thesis | year=1997 | url=https://www.proquest.com/docview/304421853|id={{ProQuest|304421853}} }}.</ref>
|-
| 2143 || {{math|1={{sfrac|3|8}} = 0.375}} || {{harvtxt|Price|1997}}<ref name="price97"/>
|-
| 1243 || {{math|1={{sfrac|3|8}} = 0.375}} || {{harvtxt|Albert|Atkinson|Handley|Holton|2002}}<ref>{{Citation
| last1=Albert | first1=Michael H. | author1-link=Michael H. Albert
| last2=Atkinson | first2=M. D. | author2-link=Michael D. Atkinson
| last3=Handley | first3=C. C.
| last4=Holton | first4=D. A.
Line 126 ⟶ 129:
| journal=[[Electronic Journal of Combinatorics]]
| volume=9
| pages=Article R5, 20 pp
| doi=10.37236/1622 | mr = 1887086
| url=http://www.combinatorics.org/Volume_9/Abstracts/v9i1r5.html| doi-access=free}}.</ref>
|-
| 1324 || conjectured to be {{math|≅ 0.244}} ||
|-
| 1342 || conjectured to be {{math|≅ 0.19658}} ||
|-
| 2413 || conjectured to be {{math|≅ 0.10474}} ||
|}
Line 157 ⟶ 160:
| pages=287–316
| doi = 10.1017/CBO9780511902499.015
| isbn=978-0-521-72834-8
}}.</ref>
Line 165 ⟶ 169:
| journal = [[Electronic Journal of Combinatorics]]
| mr = 1710623
| page = Article N1, 4 pp
| 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
Line 202 ⟶ 206:
If the entries are required to be consecutive, then the pattern is called a ''consecutive pattern''.
There are several ways in which the notion of "pattern" has been generalized. For example, a ''vincular pattern'' is a permutation containing dashes indicating which adjacent pairs of entries need not occur consecutively. For example, the permutation 314265 has two copies of the dashed pattern 2
| last1=Babson | first1=Erik
| last2= Steingrímsson | first2=Einar
| author2-link = Einar Steingrímsson
| title=Generalized permutation patterns and a classification of the Mahonian statistics
| year=2000
Line 229 ⟶ 234:
==External links==
{{Commonscat|Permutation patterns}}
* [
▲* [http://www.cs.otago.ac.nz/PermLab PermLab: software for permutation patterns], maintained by [[Michael H. Albert|Michael Albert]].
* [https://permpal.com/ PermPAL: The Permutation Pattern Avoidance Library], a database of algorithmically-derived theorems about permutation classes, maintained by Christian Bean, Émile Nadeau, Jay Pantone and Henning Ulfarsson.
| |||