A lift of West's stack-sorting map to partition diagrams

DOI10.2140/PJM.2023.324.227MaRDI QIDQ6165151zbMATH OpenFDO

Authors John Maxwell Campbell

Publication date 31 July 2023

Published in Pacific Journal of Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

permutationpermutation patternpartition monoidstack-sortingpartition diagram

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of groups and algebras (05E16)

Abstract: We introduce a lifting of West's stack-sorting map $s$ to partition diagrams, which are combinatorial objects indexing bases of partition algebras. Our lifting $mathscrS$ of $s$ is such that $mathscrS$ behaves in the same way as $s$ when restricted to diagram basis elements in the order-$n$ symmetric group algebra as a diagram subalgebra of the partition algebra $mathscr{P}_n^{xi}$. We then introduce a lifting of the notion of $1$-stack-sortability, using our lifting of $s$. By direct analogy with Knuth's famous result that a permutation is $1$-stack-sortable if and only if it avoids the pattern $231$, we prove a related pattern-avoidance property for partition diagrams, as opposed to permutations, according to what we refer to as stretch-stack-sortability.

Recommendations

• Stack-sorting preimages of permutation classes
• Sorting and preimages of pattern classes
• A survey of stack sortable permutations
• A survey of stack-sorting disciplines

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1296970 (Why is no real title available?)
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• Descents in \(t\)-sorted permutations
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Fertility monotonicity and average complexity of the stack-sorting map
• Generators and relations for partition monoids and algebras.
• Highly sorted permutations and Bell numbers
• On central idempotents in the partition algebra
• On tensor spaces for rook monoid algebras
• Partition algebras.
• Polyurethane toggles
• Stack sorting with restricted stacks
• Stack-sorting for Coxeter groups
• Stack-sorting for words
• Stack-sorting preimages of permutation classes
• Stack-sorting with consecutive-pattern-avoiding stacks
• Stack-sorting, set partitions, and Lassalle's sequence
• TEMPERLEY-LIEB ALGEBRAS FOR NON-PLANAR STATISTICAL MECHANICS — THE PARTITION ALGEBRA CONSTRUCTION
• The partition algebra and the Potts model transfer matrix spectrum in high dimensions
• The structure of the partition algebras

This page was built for publication: A lift of West's stack-sorting map to partition diagrams

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