On partially ordered patterns of length 4 and 5 in permutations
Gao, Alice L.L. and Kitaev, Sergey (2019) On partially ordered patterns of length 4 and 5 in permutations. The Electronic Journal of Combinatorics, 26 (3). P3.26. ISSN 10778926

Text (GaoKitaevEJC2019Onpartiallyorderedpatternsoflength4and5inpermutations)
Gao_Kitaev_EJC2019_On_partially_ordered_patterns_of_length_4_and_5_in_permutations.pdf Final Published Version License: Download (387kB) Preview 
Abstract
Partially ordered patterns (POPs) generalize the notion of classical patterns studied widely in the literature in the context of permutations, words, compositions and partitions. In an occurrence of a POP, the relative order of some of the elements is not important. Thus, any POP of length k is defined by a partially ordered set on k elements, and classical patterns correspond to kelement chains. The notion of a POP provides a convenient language to deal with larger sets of permutation patterns. This paper contributes to a long line of research on classical permutation patterns of length 4 and 5, and beyond, by conducting a systematic search of connections between sequences in the Online Encyclopedia of Integer Sequences (OEIS) and permutations avoiding POPs of length 4 and 5. As the result, we (i) obtain 13 new enumerative results for classical patterns of length 4 and 5, and a number of results for patterns of arbitrary length, (ii) collect under one roof many sporadic results in the literature related to avoidance of patterns of length 4 and 5, and (iii) conjecture 6 connections to the OEIS. Among the most intriguing bijective questions we state, 7 are related to explaining Wilfequivalence of various sets of patterns, e.g. 5 or 8 patterns of length 4, and 2 or 6 patterns of length 5.
Author(s):  Gao, Alice L.L. and Kitaev, Sergey ORCID: https://orcid.org/0000000333241647 

Item type:  Article 
ID code:  68863 
Keywords:  permutation pattern, partially ordered patterns, enumeration, Wilfequivalence, Electronic computers. Computer science, Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science 
Subjects:  Science > Mathematics > Electronic computers. Computer science 
Department:  Faculty of Science > Computer and Information Sciences 
Depositing user:  Pure Administrator 
Date deposited:  16 Jul 2019 13:43 
Last modified:  17 Nov 2019 01:58 
URI:  https://strathprints.strath.ac.uk/id/eprint/68863 
Export data: 