Permutation classes of polynomial growth

MH Albert, MD Atkinson, RLF Brignall

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)


A pattern class is a set of permutations closed under the formation of subpermutations. Such classes can be characterized as those permutations not involving a particular set of forbidden permutations. A simple collection of necessary and sufficient conditions on sets of forbidden permutations which ensure that the associated pattern class is of polynomial growth is determined. A catalogue of all such sets of forbidden permutations having three or fewer elements is provided together with bounds on the degrees of the associated enumerating polynomials.
Translated title of the contributionPermutation classes of polynomial growth
Original languageEnglish
Pages (from-to)249 - 264
Number of pages16
JournalAnnals of Combinatorics
Volume11 (3-4)
Publication statusPublished - Dec 2007

Bibliographical note

Publisher: Birkhäuser
Other: arXiv:math.CO/0603315

Fingerprint Dive into the research topics of 'Permutation classes of polynomial growth'. Together they form a unique fingerprint.

Cite this