Projects per year
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 (StanleyWilf 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 subkappa 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 wellorder, the substitution decomposition, and atomicity (a.k.a. the joint embedding property).
Original language  English 

Pages (fromto)  879921 
Number of pages  43 
Journal  Proceedings of the London Mathematical Society 
Volume  103 
DOIs  
Publication status  Published  Nov 2011 
Keywords
 RESTRICTED PERMUTATIONS
 ORDERED SETS
 CLOSEDSETS
 GRAPHS
Fingerprint
Dive into the research topics of 'Small permutation classes'. Together they form a unique fingerprint.Projects
 1 Finished

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A., Gent, I. P., Leonhardt, U., Mackenzie, A., Miguel, I. J., Quick, M. & Ruskuc, N.
1/09/05 → 31/08/10
Project: Standard