Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns

Claesson, Anders and Jelínek, Vít and Steingrimsson, Einar (2012) Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns. Journal of Combinatorial Theory Series A, 119 (8). pp. 1680-1691. ISSN 0097-3165 (https://doi.org/10.1016/j.jcta.2012.05.006)

Full text not available in this repository.Request a copy

Abstract

We prove that the Stanley-Wilf limit of any layered permutation pattern of length l is at most 4l(2), and that the Stanley-Wilf limit of the pattern 1324 is at most 16. These bounds follow from a more general result showing that a permutation avoiding a pattern of a special form is a merge of two permutations, each of which avoids a smaller pattern. We also conjecture that, for any k >= 0, the set of 1324-avoiding permutations with k inversions contains at least as many permutations of length n + 1 as those of length n. We show that if this is true then the Stanley-Wilf limit for 1324 is at most e(pi root 2/3) similar or equal to 13.001954.

ORCID iDs

Claesson, Anders ORCID logoORCID: https://orcid.org/0000-0001-5797-8673, Jelínek, Vít and Steingrimsson, Einar ORCID logoORCID: https://orcid.org/0000-0003-4611-0849;
CORE (COnnecting REpositories)