Projects per year
Abstract
Geometric grid classes and the substitution decomposition have both been shown to be fundamental in the understanding of the structure of permutation classes. In particular, these are the two main tools in the recent classification of permutation classes of growth rate less than κ ≈ 2.20557 (a specific algebraic integer at which infinite antichains first appear). Using language and ordertheoretic methods, we prove that the substitution closures of geometric grid classes are well partially ordered, finitely based, and that all their subclasses have algebraic generating functions. We go on to show that the inflation of a geometric grid class by a strongly rational class is well partially ordered, and that all its subclasses have rational generating functions. This latter fact allows us to conclude that every permutation class with growth rate less than κ has a rational generating function. This bound is tight as there are permutation classes with growth rate κ which have nonrational generating functions.
Original language  English 

Pages (fromto)  73108 
Number of pages  36 
Journal  Israel Journal of Mathematics 
Volume  205 
Issue number  1 
Early online date  25 Jun 2014 
DOIs  
Publication status  Published  Feb 2015 
Fingerprint
Dive into the research topics of 'Inflations of geometric grid classes of permutations'. Together they form a unique fingerprint.Projects
 2 Finished

The Structure of Permutation Classes: The Structure of Permutation Classes
21/10/11 → 20/10/14
Project: Standard

Automata Languages Decidability: Automata, Languages, Decidability in Algebra
1/03/10 → 31/05/14
Project: Standard