We introduce a sorting machine consisting of $k+1$ stacks in series: the first $k$ stacks can only contain elements in decreasing order from top to bottom, while the last one has the opposite restriction. This device generalizes the $\mathfrak{DI}$ machine introduced by Rebecca Smith, which studies the case $k=1$. Here we show that, for $k=2$, the set of sortable permutations is a class with infinite basis, by explicitly finding an antichain of minimal nonsortable permutations. This construction can easily be adapted to each $k\geqslant 3$. Next we describe an optimal sorting algorithm, again for the case $k=2$. We then analyze two types of left-greedy sorting procedures, obtaining complete results in one case and only some partial results in the other one. We close the paper by discussing a few open questions.
@article{10_37236_9154,
author = {Giulio Cerbai and Lapo Cioni and Luca Ferrari},
title = {Stack sorting with increasing and decreasing stacks},
journal = {The electronic journal of combinatorics},
year = {2020},
volume = {27},
number = {1},
doi = {10.37236/9154},
zbl = {1430.68063},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9154/}
}
TY - JOUR
AU - Giulio Cerbai
AU - Lapo Cioni
AU - Luca Ferrari
TI - Stack sorting with increasing and decreasing stacks
JO - The electronic journal of combinatorics
PY - 2020
VL - 27
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/9154/
DO - 10.37236/9154
ID - 10_37236_9154
ER -
%0 Journal Article
%A Giulio Cerbai
%A Lapo Cioni
%A Luca Ferrari
%T Stack sorting with increasing and decreasing stacks
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9154/
%R 10.37236/9154
%F 10_37236_9154
Giulio Cerbai; Lapo Cioni; Luca Ferrari. Stack sorting with increasing and decreasing stacks. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/9154
