Catalan monoids, monoids of local endomorphisms, and their presentations
type: Item
instance of: scholarly article
title: Catalan monoids, monoids of local endomorphisms, and their presentations
zbMATH Open document ID: 0862.20049
DOI: 10.1007/BF02574150
author: Andrew Solomon
published in: Semigroup Forum
publication date: 1997-05-26T00:00:00Z
full work available at URL: https://eudml.org/doc/135498
review text: 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.
Mathematics Subject Classification ID: 20M20
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 943675
zbMATH Keywords: endomorphisms of graphs
zbMATH Keywords: semigroups of order-preserving mappings
zbMATH Keywords: directed graphs
zbMATH Keywords: finite semigroups
zbMATH Keywords: Catalan monoids of finite graphs
zbMATH Keywords: presentations
zbMATH Keywords: trees
describes a project that uses: Magma
MaRDI profile type: Publication
cites work: On the ranks of certain semigroups of order-preserving transformations
cites work: Combinatorial results for semigroups of order-preserving mappings
cites work: DIVISORS OF SEMIGROUPS OF ORDER-PRESERVING MAPPINGS ON A FINITE CHAIN
cites work: The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup
cites work: Q4126563
cites work: Q4348014
cites work: Q5639839
cites work: Semigroups of mappings on graphs
cites work: Q3769981
cites work: Q5589310
description: scientific article; zbMATH DE number 943675