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 1077-8926 (https://www.combinatorics.org/ojs/index.php/eljc/a...)

[thumbnail of Gao-Kitaev-EJC2019-On-partially-ordered-patterns-of-length-4-and-5-in-permutations]
Preview
 Text. Filename: Gao_Kitaev_EJC2019_On_partially_ordered_patterns_of_length_4_and_5_in_permutations.pdf
Final Published Version
License: Creative Commons Attribution-NoDerivatives 4.0 logo
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 k-element 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 Wilf-equivalence of various sets of patterns, e.g. 5 or 8 patterns of length 4, and 2 or 6 patterns of length 5.

CORE (COnnecting REpositories)