کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4624632 1631633 2015 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Splittings and Ramsey properties of permutation classes
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Splittings and Ramsey properties of permutation classes
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Applied Mathematics - Volume 63, February 2015, Pages 41–67
نویسندگان
, ,