
arXiv: 2005.07187
Sch��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 $\partial^{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 $0\leq k\leq n-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.
16 pages, 4 figures
Combinatorics, FOS: Mathematics, Mathematics - Combinatorics, Order, lattices, ordered algebraic structures, Combinatorics (math.CO), 06A07, 05A15, 05A05
Combinatorics, FOS: Mathematics, Mathematics - Combinatorics, Order, lattices, ordered algebraic structures, Combinatorics (math.CO), 06A07, 05A15, 05A05
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
