Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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

Full text not available in this repository. (Request a copy from the Strathclyde author)

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.

Item type: Article
ID code: 42133
Keywords: upper bounds , stanley-wilf limit , layered patterns, pattern avoidance, layered permutations , Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 19 Nov 2012 14:20
    Last modified: 15 Dec 2012 16:37
    URI: http://strathprints.strath.ac.uk/id/eprint/42133

    Actions (login required)

    View Item