Catalan monoids, monoids of local endomorphisms, and their presentations (Q1815355)

For a directed graph \(G=(V,E)\) the mapping \(\overline{f}_s:V\to V\), where \(s=(a,b)\in E\), is defined as follows: \(a\mapsto b\) and \(x\mapsto x\) if \(x\in V \setminus \{a\}\). The author introduces the Catalan monoid \({\mathcal C}(G)\) as the monoid generated by all \(\overline{f}_s\), \(s\in E\). The partial Catalan monoid \({\mathcal P}C(G)\) consists of restrictions of mappings from \({\mathcal C}(G)\) on subsets of \(V\). Every finite semigroup can be embedded into the Catalan monoid of a finite graph. The semigroups \(O_n\) [\(C_n\)] of all order-preserving [of all order-preserving non-increasing] mappings on a chain of length \(n\) are examples of Catalan monoids. The main result is a presentation of \({\mathcal C}(G)\) and \({\mathcal P}C(G)\) of a tree \(G\); thus several known results for \(O_n\), e.g. \textit{A. Ya. Ajzenshtat} [Sib. Mat. Zh. 3, 161-169 (1962; Zbl 0114.01702)] and \textit{P. M. Higgins} [Int. J. Algebra Comput. 5, No. 6, 725-742 (1995; Zbl 0842.20054)], and \(C_n\) are obtained as corollaries.