$k$-Pop Stack Sortable Permutations and $2$-Avoidance

Abstract

We consider permutations sortable by $k$ passes through a deterministic pop stack. We show that for any $k\in\mathbb{N}$ the set is characterised by finitely many patterns, answering a question of Claesson and Guðmundsson. Moreover, these sets of patterns are algorithmically constructible.

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 $2$-avoidance.