کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4624632 | 1631633 | 2015 | 27 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Splittings and Ramsey properties of permutation classes Splittings and Ramsey properties of permutation classes](/preview/png/4624632.png)
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.
Journal: Advances in Applied Mathematics - Volume 63, February 2015, Pages 41–67