On the inverse image of pattern classes under bubble sort

DOI10.4310/JOC.2011.V2.N2.A3zbMATH Open1247.05005MaRDI QIDQ433475FDOQ433475

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)

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

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)