On the inverse image of pattern classes under bubble sort

DOI10.4310/JOC.2011.V2.N2.A3MaRDI QIDQ433475zbMATHFDO

Authors Mike Atkinson, Mathilde Bouvel, Anders Claesson, Mark Dukes, Michael Albert

Publication date 16 July 2012

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.5299

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Searching and sorting (68P10)

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.

Recommendations

• Two permutation classes related to the bubble sort operator
• Bubblesort, stacksort and their duals
• Sorting and preimages of pattern classes
• Preimages under the bubblesort operator
• Operators of equivalent sorting power and related Wilf-equivalences

Cited in

(9)

• Bubblesort, stacksort and their duals
• Pop-stack-sorting for Coxeter groups
• Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry
• Preimages under the bubblesort operator
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Two first-order logics of permutations
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Two permutation classes related to the bubble sort operator
• Dynamics of pop-tsack torsing

This page was built for publication: On the inverse image of pattern classes under bubble sort

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433475)