António Malheiro

The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. For certain monoids connected with combinatorics, such as the plactic monoid (the monoid of Young tableaux) and the sylvester monoid (the monoid of binary search trees), connected components consist of elements that have the same evaluation (that is, contain the same number of each generating symbol). This paper discusses new results on the diameters of connected components of the cyclic shift graphs of the finite-rank analogues of these monoids, showing that the maximum diameter of a connected component is dependent only on the rank. The proof techniques are explained in the case of the sylvester monoid.

This paper studies complete rewriting systems and biautomaticity for three interesting classes of finite-rank homogeneous monoids: Chinese monoids, hypoplactic monoids, and sylvester monoids. For Chinese monoids, we first give new presentations via finite complete rewriting systems, using more lucid constructions and proofs than those given independently by Chen & Qui and Güzel Karpuz; we then construct biautomatic structures. For hypoplactic monoids, we construct finite complete rewriting systems and biautomatic structures. For sylvester monoids, which are not finitely presented, we prove that the standard presentation is an infinite complete rewriting system, and construct biautomatic structures. Consequently, the monoid algebras corresponding to monoids of these classes are automaton algebras in the sense of Ufnarovskij.

Crystal graphs, in the sense of Kashiwara, carry a natural monoid structure given by identifying words labelling vertices that appear in the same position of isomorphic components of the crystal. In the particular case of the crystal graph for the q-analogue of the special linear Lie algebra sln, this monoid is the celebrated plactic monoid, whose elements can be identified with Young tableaux. The crystal graph and the so-called Kashiwara operators interact beautifully with the combinatorics of Young tableaux and with the Robinson--Schensted correspondence and so provide powerful combinatorial tools to work with them. This paper constructs an analogous `quasi-crystal' structure for the hypoplactic monoid, whose elements can be identified with quasi-ribbon tableaux and whose connection with the theory of quasi-symmetric functions echoes the connection of the plactic monoid with the theory of symmetric functions. This quasi-crystal structure and the associated quasi-Kashiwara operators are shown to interact just as neatly with the combinatorics of quasi-ribbon tableaux and with the hypoplactic version of the Robinson--Schensted correspondence. A study is then made of the interaction of the crystal graph of the plactic monoid and the quasi-crystal graph for the hypoplactic monoid. Finally, the quasi-crystal structure is applied to prove some new results about the hypoplactic monoid.

The cyclic shift graph of a monoid is the graph whose vertices are the elements of the monoid and whose edges connect elements that are cyclic shift related. The Patience Sorting algorithm admits two generalizations to words, from which two kinds of monoids arise, the $\belr$ monoid and the $\bell$ (also known as Bell) monoid. Like other monoids arising from combinatorial objects such as the plactic and the sylvester, the connected components of the cyclic shift graph of the $\belr$ monoid consists of elements that have the same number of each of its composing symbols. In this paper, with the aid of the computational tool SageMath, we study the diameter of the connected components from the cyclic shift graph of the $\belr$ monoid.

Within the theory of monoids, the cyclic shift relation, among other relations, generalizes the relation of conjugacy for groups. We examine several of these relations for both the $\belr$ and the $\bell$ monoids.

The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. This paper examines the cyclic shift graphs of `plactic-like' monoids, whose elements can be viewed as combinatorial objects of some type: aside from the plactic monoid itself (the monoid of Young tableaux), examples include the hypoplactic monoid (quasi-ribbon tableaux), the sylvester monoid (binary search trees), the stalactic monoid (stalactic tableaux), the taiga monoid (binary search trees with multiplicities), and the Baxter monoid (pairs of twin binary search trees). It was already known that for many of these monoids, connected components of the cyclic shift graph consist of elements that have the same
evaluation (that is, contain the same number of each generating symbol). This paper focusses on the maximum diameter of a connected component of the cyclic shift graph of these monoids in the rank-$n$ case. For the hypoplactic monoid, this is $n-1$; for the sylvester and taiga monoids, at least $n-1$ and at most $n$; for the stalactic monoid, $3$ (except for ranks $1$ and $2$, when it is respectively $0$ and $1$); for the plactic monoid, at least $n-1$ and at most $2n-3$. The current state of knowledge, including new and previously-known results, is summarized in a table.

A semigroup is amiable if there is exactly one idempotent in each ℛ*-class and in each ℒ*-class. A semigroup is adequate if it is amiable and if its idempotents commute. We characterize adequate semigroups by showing that they are precisely those amiable semigroups that do not contain isomorphic copies of two particular non-adequate semigroups as subsemigroups.

There have been several attempts to extend the notion of conjugacy from groups to monoids.
The aim of this paper is study the decidability and independence of conjugacy problems
for three of these notions (which we will denote by $\sim_p$, $\sim_o$, and $\sim_c$) in
certain classes of finitely presented monoids. We will show that in the class of polycyclic monoids,
$p$-conjugacy is ``almost'' transitive, $\sim_c$ is strictly included in $\sim_p$, and
the $p$- and $c$-conjugacy problems are decidable with linear compexity.
For other classes of monoids, the situation is more complicated.
We show that there exists a monoid $M$ defined by a finite complete
presentation such that the $c$-conjugacy problem for $M$ is undecidable, and
that for finitely presented monoids, the $c$-conjugacy problem and the word
problem are independent, as are the $c$-conjugacy and $p$-conjugacy problems.

n/a

The action of any group on itself by conjugation and the corresponding conjugacy relation play an important role in group theory. There have been several attempts to extend the notion of conjugacy to semigroups. In this paper, we present a new definition of conjugacy that can be applied to an arbitrary semigroup and it does not reduce to the universal relation in semigroups with a zero. We compare the new notion of conjugacy with existing definitions, characterize the conjugacy in various semigroups of transformations on a set, and count the number of conjugacy classes in these semigroups when the set is infinite.

We prove that given a finite (zero) exact right decomposition (M, T) of a semigroup S, if M is defined by a finite complete presentation, then S is also defined by a finite complete presentation. Exact right decompositions are natural generalizations to semigroups of coset decompositions in groups. As a consequence, we deduce that any Zappa–Szép extension of a monoid defined by a finite complete presentation, by a finite monoid, is also defined by such a presentation.

It is also proved that a semigroup M^0[A; I, J; P], where A and P satisfy some very general conditions, is also defined by a finite complete presentation.

We exhibit faithful representations of the hypoplactic, stalactic, taiga, sylvester, Baxter and right patience sorting monoids of each finite rank as monoids of upper triangular matrices over any semiring from a large class including the tropical semiring and fields of characteristic 0. By analysing the image of these representations, we show that the variety generated by a single hypoplactic (respectively, stalactic or taiga) monoid of rank at least 2 coincides with the variety generated by the natural numbers together with a fixed finite monoid (respectively, F) and forms a proper subvariety of the variety generated by the plactic monoid of rank 2.