Permutation pattern: Difference between revisions

Revision as of 13:37, 9 November 2022

Revision as of 23:33, 23 January 2023

Line 47:

| 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| arxiv = 0805.1325| title=Classification of bijections between 321- and 132-avoiding permutations| year=2008| journal=[[Séminaire Lotharingien de Combinatoire]]| url = http://www.emis.de/journals/SLC/wpapers/s60claekit.pdf| volume=60| pages=B60d| doi=10.48550/arXiv.0805.1325| mr = 2465405| bibcode=2008arXiv0805.1325C}}.</ref>

In general, if |''Av_n''(''β'')| = |''Av_n''(''σ'')| for all ''n'', then ''β'' and ''σ'' are said to be [[Wilf equivalence|''Wilf-equivalent'']]. Many Wilf-equivalences stem from the trivial fact that |''Av_n''(''β'')| = |''Av_n''(''β''^&minus;1)| = |''Av_n''(''β''^rev)| for all ''n'', where ''β''^&minus;1 denotes the [[Permutation#Product and inverse|inverse]] of ''β'' and ''β''^rev 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₈]] with a natural action on [[permutation matrices]].) However, there are also numerous examples of nontrivial Wilf-equivalences (such as that between ''123'' and ''231''):

Line 86:

Given a permutation <math>\tau</math> (called the ''text'') of length <math>n</math> and another permutation <math>\pi</math> of length <math>k</math> (called the ''pattern''), the ''permutation pattern matching (PPM)'' problem asks whether <math>\pi</math> is contained in <math>\tau</math>. When both <math>n</math> and <math>k</math> are regarded as variables, the problem is known to be [[NP-complete]], and the problem of counting the number of such matches is [[Sharp-P-complete|#P-complete]].<ref>{{citation|last1=Bose|first1=Prosenjit|author1-link=Jit Bose|last2=Buss|first2=Jonathan F.|last3=Lubiw|first3=Anna|author3-link=Anna Lubiw|title=Pattern matching for permutations|journal=[[Information Processing Letters]]|date=March 1998|volume=65|issue=5|pages=277–283|doi=10.1016/S0020-0190(97)00209-3}}</ref> However, PPM can be solved in [[linear time]] when ''k'' is a constant. Indeed, Guillemot and Marx<ref>{{cite journal|last=Guillemot|first=Sylvain|author2=Marx, Daniel|title=Finding small patterns in permutations in linear time|journal=Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms|year=2014|page=20|doi=10.1137/1.9781611973402.7|arxiv=1307.3073|isbn=978-1-61197-338-9|s2cid=1846959}}</ref> showed that PPM can be solved in time <math>2^{O(k^2\log k)} \cdot n</math>, meaning that it is [[fixed-parameter tractable]] with respect to <math>k</math>.

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|doi=10.48550/arXiv.1301.0340 |arxiv=1301.0340|bibcode=2013arXiv1301.0340B}}</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>

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}}</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|bibcode=2015arXiv151006051A|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>.

== Packing densities ==