Splittability and 1-amalgamability of permutation classes
Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2
Voir la notice de l'article provenant de la source Episciences
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.
@article{DMTCS_2018_19_2_a0,
author = {Jel{\'\i}nek, V{\'\i}t and Opler, Michal},
title = {Splittability and 1-amalgamability of permutation classes},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {19},
number = {2},
year = {2017-2018},
doi = {10.23638/DMTCS-19-2-4},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-4/}
}
TY - JOUR AU - Jelínek, Vít AU - Opler, Michal TI - Splittability and 1-amalgamability of permutation classes JO - Discrete mathematics & theoretical computer science PY - 2017-2018 VL - 19 IS - 2 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-4/ DO - 10.23638/DMTCS-19-2-4 LA - en ID - DMTCS_2018_19_2_a0 ER -
%0 Journal Article %A Jelínek, Vít %A Opler, Michal %T Splittability and 1-amalgamability of permutation classes %J Discrete mathematics & theoretical computer science %D 2017-2018 %V 19 %N 2 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-2-4/ %R 10.23638/DMTCS-19-2-4 %G en %F DMTCS_2018_19_2_a0
Jelínek, Vít; Opler, Michal. Splittability and 1-amalgamability of permutation classes. Discrete mathematics & theoretical computer science, Permutation Patterns 2016, Tome 19 (2017-2018) no. 2. doi: 10.23638/DMTCS-19-2-4
Cité par Sources :