On the inverse image of pattern classes under bubble sort

Abstract

Let B be the operation of re-ordering a sequence by one pass of bubble sort. We completely answer the question of when the inverse image of a principal pattern class under B is a pattern class.

11 pages