Vít Jelínek ; Michal Opler - Splittability and 1-amalgamability of permutation classes

dmtcs:3292 - Discrete Mathematics & Theoretical Computer Science, December 5, 2017, Vol. 19 no. 2, Permutation Patterns 2016 - https://doi.org/10.23638/DMTCS-19-2-4
Splittability and 1-amalgamability of permutation classesArticle

Authors: Vít Jelínek ORCID; Michal Opler

    A permutation class $C$ is splittable if it is contained in a merge of two of its proper subclasses, and it is 1-amalgamable if given two permutations $\sigma$ and $\tau$ in $C$, each with a marked element, we can find a permutation $\pi$ in $C$ containing both $\sigma$ and $\tau$ such that the two marked elements coincide. It was previously shown that unsplittability implies 1-amalgamability. We prove that unsplittability and 1-amalgamability are not equivalent properties of permutation classes by showing that the class $Av(1423, 1342)$ is both splittable and 1-amalgamable. Our construction is based on the concept of LR-inflations, which we introduce here and which may be of independent interest.

    Volume: Vol. 19 no. 2, Permutation Patterns 2016
    Section: Permutation Patterns
    Published on: December 5, 2017
    Accepted on: November 21, 2017
    Submitted on: May 1, 2017
    Keywords: Mathematics - Combinatorics,05A05

    1 Document citing this article

    Consultation statistics

    This page has been seen 501 times.
    This article's PDF has been downloaded 270 times.