2022/08/18 by Eliot Hodges, Hodges, Eliot
Computer Science · Mathematics · #semigroups and automata theory #Advanced Graph Theory Research #Advanced Combinatorial Mathematics
paper · pdf · doi:10.48550/arxiv.2208.08665
In 2022, Defant and Kravitz introduced extended promotion (denoted ∂), a map that acts on the set of labelings of a poset. Extended promotion is a generalization of Schützenberger's promotion operator, a well-studied map that permutes the set of linear extensions of a poset. It is known that if L is a labeling of an n-element poset P, then ∂n-1(L) is a linear extension. This allows us to regard ∂ as a sorting operator on the set of all labelings of P, where we think of the linear extensions of P as the labelings which have been sorted. The labelings requiring n-1 applications of ∂ to be sorted are called tangled; the labelings requiring n-2 applications are called quasi-tangled. In addition to computing the sizes of the fibers of promotion for rooted tree posets, we count the quasi-tangled labelings of a relatively large class of posets called inflated rooted trees with deflated leaves. Given an n-element poset with a unique minimal element with the property that the minimal element has exactly one parent, it follows from the aforementioned enumeration that this poset has 2(n-1)!-(n-2)! quasi-tangled labelings. Using similar methods, we outline an algorithmic approach to enumerating the labelings requiring n-k-1 applications to be sorted for any fixed k∈\1,…,n-2\. We also make partial progress towards proving a conjecture of Defant and Kravitz on the maximum possible number of tangled labelings of an n-element poset.