On the inverse image of pattern classes under bubble sort

DOI10.4310/JOC.2011.V2.N2.A3zbMATH Open1247.05005arXiv1008.5299MaRDI 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)

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.

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

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

Mathematics Subject Classification ID

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

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)