Permutation classes of polynomial growth

MH Albert; MD Atkinson; RLF Brignall

doi:10.1007/s00026-007-0318-x

Permutation classes of polynomial growth

MH Albert
, MD Atkinson
, RLF Brignall

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

8 Citations (Scopus)

Abstract

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 contribution	Permutation classes of polynomial growth
Original language	English
Pages (from-to)	249 - 264
Number of pages	16
Journal	Annals of Combinatorics
Volume	11 (3-4)
DOIs	https://doi.org/10.1007/s00026-007-0318-x
Publication status	Published - Dec 2007

Bibliographical note

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

Access to Document

10.1007/s00026-007-0318-x

http://www.springerlink.com/content/d754572273516024/

Handle.net

Persistent link

Cite this

@article{685bf8a399774b0e897302b74e16aebb,

title = "Permutation classes of polynomial growth",

abstract = "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.",

author = "MH Albert and MD Atkinson and RLF Brignall",

note = "Publisher: Birkh{\"a}user Other: arXiv:math.CO/0603315",

year = "2007",

month = dec,

doi = "10.1007/s00026-007-0318-x",

language = "English",

volume = "11 (3-4)",

pages = "249 -- 264",

journal = "Annals of Combinatorics",

issn = "0219-3094",

publisher = "Birkhauser Verlag Basel",

}

TY - JOUR

T1 - Permutation classes of polynomial growth

AU - Albert, MH

AU - Atkinson, MD

AU - Brignall, RLF

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

PY - 2007/12

Y1 - 2007/12

N2 - 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.

AB - 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.

U2 - 10.1007/s00026-007-0318-x

DO - 10.1007/s00026-007-0318-x

M3 - Article (Academic Journal)

SN - 0219-3094

VL - 11 (3-4)

SP - 249

EP - 264

JO - Annals of Combinatorics

JF - Annals of Combinatorics

ER -

Permutation classes of polynomial growth

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this