Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4624632 | Advances in Applied Mathematics | 2015 | 27 Pages |
We say that a permutation π is merged from permutations ρ and τ, if we can color the elements of π red and blue so that the red elements are order-isomorphic to ρ and the blue ones to τ. A permutation class is a set of permutations closed under taking subpermutations. A permutation class C is splittable if it has two proper subclasses A and B such that every element of C can be obtained by merging an element of A with an element of B.Splittability of specific permutation classes has recently been applied as a tool in deriving enumerative results. The goal of this paper is to establish general criteria for splittability and unsplittability. As our main results, we show that if σ is a sum-decomposable permutation of order at least four, then the class Av(σ)Av(σ) of all σ-avoiding permutations is splittable, while if σ is a simple permutation, then Av(σ)Av(σ) is unsplittable.