$k$-pop stack sortable permutations and $2$-avoidance


Abstract in English

We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $kinmathbb N$ the set is characterised by finitely many patterns, answering a question of Claesson and Gu{dh}mundsson. Our characterisation demands a more precise definition than in previous literature of what it means for a permutation to avoid a set of barred and unbarred patterns. We propose a new notion called emph{$2$-avoidance}.

Download