Small permutation classes

Vincent Vatter*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Citations (Scopus)

Abstract

We establish a phase transition for permutation classes (downsets of permutations under the permutation containment order): there is an algebraic number kappa, approximately 2.20557, for which there are only countably many permutation classes of growth rate (Stanley-Wilf limit) less than kappa but uncountably many permutation classes of growth rate kappa, answering a question of Klazar. We go on to completely characterize the possible sub-kappa growth rates of permutation classes, answering a question of Kaiser and Klazar. Central to our proofs are the concepts of generalized grid classes (introduced herein), partial well-order, the substitution decomposition, and atomicity (a.k.a. the joint embedding property).

Original languageEnglish
Pages (from-to)879-921
Number of pages43
JournalProceedings of the London Mathematical Society
Volume103
DOIs
Publication statusPublished - Nov 2011

Keywords

  • RESTRICTED PERMUTATIONS
  • ORDERED SETS
  • CLOSED-SETS
  • GRAPHS

Fingerprint

Dive into the research topics of 'Small permutation classes'. Together they form a unique fingerprint.

Cite this