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

John M. Campbell

Vol. 324 (2023), No. 2, 227–248

DOI: 10.2140/pjm.2023.324.227

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 $\mathcal{𝒮}$ of $s$ is such that $\mathcal{𝒮}$ 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 ${\mathcal{𝒫}}_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.

Keywords

stack-sorting, partition diagram, permutation, permutation pattern, partition monoid

Mathematical Subject Classification

Primary: 05A05

Secondary: 05E16

Milestones

Received: 11 December 2022

Revised: 15 April 2023

Accepted: 21 May 2023

Published: 26 July 2023