The Stylic Monoid

DOI10.1007/S00233-022-10285-3MaRDI QIDQ6370098arXivFDO

Authors Antoine Abram, Christophe Reutenauer

Publication date 11 June 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00233-022-10285-3

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Ordered semigroups and monoids (06F05) Ordered rings, algebras, modules (06F25) Algebraic monoids (20M32)

arXiv classification

math.CO

Abstract: The free monoid $A^{\ast }$ on a finite totally ordered alphabet $A$ acts at the left on columns, by Schensted left insertion. This defines a finite monoid, denoted $Styl(A)$ and called the stylic monoid. It is canonically a quotient of the plactic monoid. Main results are: the cardinality of $Styl(A)$ is equal to the number of partitions of a set on $|A|+1$ elements. We give a bijection with so-called $N$-tableaux, similar to Schensted's algorithm, explaining this fact. Presentation of $Styl(A)$: it is generated by $A$ subject to the plactic (Knuth) relations and the idempotent relations $a^2=a$, $ainA$. The canonical involutive anti-automorphism on $A^{\ast }$, which reverses the order on $A$, induces an involution of $Styl(A)$, which similarly to the corresponding involution of the plactic monoid, may be computed by an evacuation-like operation (Sch"utzenberger involution on tableaux) on so-called standard immaculate tableaux (which are in bijection with partitions). The monoid $Styl(A)$ is $J$-trivial, and the $J$-order of $Styl(A)$ is graded: the co-rank is given by the number of elements in the $N$-tableau. The monoid $Styl(A)$ is the syntactic monoid for the the function which associates to each word $win{A}^{\ast }$ the length of its longest strictly decreasing subword.

This page was built for publication: The Stylic Monoid

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