Inflations of geometric grid classes of permutations

Details Inflations of geometric grid classes of permutations Inflations of geometric grid classes of permutations

2012-02-08

arxiv.org/abs/1202.1833v1

Mathematics

Combinatorics

Scientific paper

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 $\kappa\approx2.20557$ (a specific algebraic integer at which infinite antichains begin to appear). Using language- and order-theoretic methods, we prove that the substitution closures of geometric grid classes are partially well-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 partially well-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 $\kappa$ has a rational generating function. This bound is tight as there are permutation classes with growth rate $\kappa$ which have nonrational generating functions.

Affiliated with

Also associated with

No associations

Rating

Inflations of geometric grid classes of permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inflations of geometric grid classes of permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inflations of geometric grid classes of permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-156155