Article ID Journal Published Year Pages File Type
4624632 Advances in Applied Mathematics 2015 27 Pages PDF
Abstract

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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, ,