2020/05/14 by Colin Defant, Defant, Colin, Noah Kravitz +1
Computer Science · Mathematics · #05A05 #05A15 #06A07 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2005.07187
openalex publication_date 2020/05/14 · openalex created_date 2024/04/10 · openalex updated_date 2026/07/28
Schützenberger's promotion operator is an extensively-studied bijection that permutes the linear extensions of a finite poset. We introduce a natural extension ∂ of this operator that acts on all labelings of a poset. We prove several properties of ∂; in particular, we show that for every labeling L of an n-element poset P, the labeling ∂n-1(L) is a linear extension of P. Thus, we can view the dynamical system defined by ∂ as a sorting procedure that sorts labelings into linear extensions. For all 0≤ k≤ n-1, we characterize the n-element posets P that admit labelings that require at least n-k-1 iterations of ∂ 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 ∂(L) is a linear extension.