Pattern Avoidance Classes and Subpermutations

M. D. Atkinson, M. M. Murphy, N. Ruškuc


Pattern avoidance classes of permutations that cannot be expressed as unions of proper subclasses can be described as the set of subpermutations of a single bijection. In the case that this bijection is a permutation of the natural numbers a structure theorem is given. The structure theorem shows that the class is almost closed under direct sums or has a rational generating function.

Full Text: