Stack sorting with increasing and decreasing stacks (Q2288161)

Summary: 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.