Promotion sorting

DOI10.1007/S11083-022-09603-9MaRDI QIDQ6105040zbMATH OpenFDO

Authors Colin Defant, Noah Kravitz

Publication date 26 June 2023

Published in Order (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics (05-XX) Order, lattices, ordered algebraic structures (06-XX)

Abstract: Sch"{u}tzenberger's promotion operator is an extensively-studied bijection that permutes the linear extensions of a finite poset. We introduce a natural extension $partial$ of this operator that acts on all labelings of a poset. We prove several properties of $partial$; in particular, we show that for every labeling $L$ of an $n$-element poset $P$, the labeling $partia{l}^{n-1}(L)$ is a linear extension of $P$. Thus, we can view the dynamical system defined by $partial$ as a sorting procedure that sorts labelings into linear extensions. For all $0leqkleqn-1$, we characterize the $n$-element posets $P$ that admit labelings that require at least $n-k-1$ iterations of $partial$ in order to become linear extensions. The case in which $k=0$ concerns labelings that require the maximum possible number of iterations in order to be sorted; we call these labelings tangled. We explicitly enumerate tangled labelings for a large class of posets that we call inflated rooted forest posets. For an arbitrary finite poset, we show how to enumerate the sortable labelings, which are the labelings $L$ such that $partial(L)$ is a linear extension.

Cites work

• 2N noncollinear points determine at least 2N directions
• Balanced tableaux
• Cyclic descents for general skew tableaux
• Cyclic sieving, promotion, and representation theory
• Descent polynomials for permutations with bounded drop size
• Dual equivalence with applications, including a conjecture of Proctor
• Evacuation of labelled graphs
• Flip-sort and combinatorial aspects of pop-stack sorting
• scientific article; zbMATH DE number 4047729 (Why is no real title available?)
• scientific article; zbMATH DE number 3587058 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• Permutations sortable by \(n - 4\) passes through a stack
• Promotion and cyclic sieving via webs
• Promotion and evacuation
• Promotion des morphismes d'ensembles ordonnes
• Quelques remarques sur une Construction de Schensted.
• Rowmotion and increasing labeling promotion
• Solution of the Bulgarian Solitaire Conjecture
• The cycling of partitions and composition under repeated shifts
• Young tableaux and Solitaire bulgare

Cited in

(7)

• Stack-sorting with consecutive-pattern-avoiding stacks
• Meeting covered elements in -Tamari lattices
• Toric promotion
• Effective Poset Inequalities
• Linear extensions and shelling orders
• Permutoric promotion: gliding globs, sliding stones, and colliding coins
• Promotion, tangled labelings, and sorting generating functions

This page was built for publication: Promotion sorting

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