Presentations for monoids of endomorphisms of a star graph

Vítor H. Fernandes, Jörg Koppitz and T. Musunthia · 2025

Read Presentations for monoids of endomorphisms of a star graph by Vítor H. Fernandes, Jörg Koppitz and T. Musunthia (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00222.txt.

Introduction

Vitor Fernandes, Jörg Koppitz, and Tiwadee Musunthia study maps on a star graph in a paper the text dates to 2024. A star graph has one center joined to every outer point and no other links. The authors look at monoids, sets of maps closed under chaining, built from maps that respect the graph's links to varying degrees.

Four families are covered: all endomorphisms, weak ones, strong ones, and maps that are both strong and weak. Each family forms its own monoid with its own rules. The paper's main goal is to give, for each monoid, a presentation: a short list of generators and relations from which every map and every rule of chaining can be rebuilt.

Catalog record

CREATORVítor H. Fernandes, Jörg Koppitz and T. Musunthia
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-00222

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Presentations for monoids of endomorphisms of a star graph Vítor H. Fernandes, Jörg Koppitz and T. Musunthia Abstract In this paper, we consider the monoids of all endomorphisms, of all weak endomorphisms, of all strong endomorphisms and of all strong weak endomorphisms of a star graph with a finite number of vertices. Our main objective is to exhibit a presentation for each of them. 2020 Mathematics subject classification: 20M20, 20M05, 05C12, 05C25. Keywords: transformations, partial endomorphisms, star graphs, presentations. Introduction For a set \Omega , denote by \mathscr{PT}(\Omega) the monoid (under composition) of all partial transformations on \Omega , by \mathscr{T}(\Omega) the submonoid of \mathscr{PT}(\Omega) of all full transformations on \Omega and by \mathscr{S}(\Omega) the symmetric group on \Omega , i.e. the subgroup of \mathscr{PT}(\Omega) of all permutations on \Omega . Let G=(V,E) be a simple graph (i.e. undirected, without loops and without multiple edges). Let \alpha be a full transformation of V . We say that \alpha is: • an endomorphism of G if \{u,v\}\in E implies \{u\alpha,v\alpha\}\in E , for all u,v\in V ; • a weak endomorphism of G if \{u,v\}\in E and u\alpha\neq v\alpha imply \{u\alpha,v\alpha\}\in E , for all u,v\in V ; • a strong endomorphism of G if \{u,v\}\in E if and only if \{u\alpha,v\alpha\}\in E , for all u,v\in V ; • a strong weak endomorphism of G if \{u,v\}\in E and u\alpha\neq v\alpha if and only if \{u\alpha,v\alpha\}\in E , for all u,v\in V ; • an automorphism of G if \alpha is a bijective strong endomorphism (i.e. \alpha is bijective and \alpha and \alpha^{-1} are both endomorphisms). For finite graphs, any bijective week endomorphism is an automorphism. Denote by: • \mathrm{End}G the set of all endomorphisms of G ; • \mathrm{wEnd}G the set of all weak endomorphisms of G ; • \mathrm{sEnd}G the set of all strong endomorphisms of G ; • \mathrm{swEnd}G the set of all strong weak endomorphisms of G ; • \mathrm{Aut}G the set of all automorphisms of G . Clearly, \mathrm{End}G , \mathrm{wEnd}G , \mathrm{sEnd}G , \mathrm{swEnd}G and \mathrm{Aut}G are monoids under composition of mappings with the identity mapping \mathrm{id} as the identity element. Moreover, \mathrm{Aut}G is also a group. It is also clear that \mathrm{Aut}G\subseteq\mathrm{sEnd}G\subseteq\mathrm{End}G,\mathrm{swEnd}G\subseteq\mathrm{wEnd}G \bullet \bullet \bullet \bullet \bullet \mathrm{Aut}G \mathrm{sEnd}G \mathrm{swEnd}G \mathrm{End}G \mathrm{wEnd}G (these inclusions may not be strict). Monoids of endomorphisms of graphs have many important applications, particularly related to automata theory; see [ 21 ] . A large number of interesting results concerning graphs and algebraic properties of their endomorphism monoids have been obtained by several authors (see, for example, [ 3 , 10 , 17 , 18 , 22 , 23 , 25 , 30 ] ). In recent years, the first two authors together with Dimitrova and Quinteiro, also have studied such types of monoids, in particular by considering finite undirected paths and cycles; see [ 6 , 7 , 8 ] . For any non negative integer n , let \Omega_{n}=\{1,2,\ldots,n\} and \Omega_{n}^{0}=\{0,1,\ldots,n\}=\{0\}\cup\Omega_{n} . Notice that, \Omega_{0}=\emptyset and \Omega_{0}^{0}=\{0\} . For an integer n\geqslant 1 , consider the star graph S_{n}=(\Omega_{n-1}^{0},\{\{0,i\}\mid 1\leqslant i\leqslant n-1\}) with n vertices. \bullet \bullet \bullet \bullet \bullet \bullet \bullet \scriptstyle 5 \scriptstyle 1 \scriptstyle n-2 \scriptstyle 3 \scriptstyle 4 \scriptstyle 2 \scriptstyle n-1 \bullet \scriptstyle 0 These very basic graphs, which are special examples of trees and also of complete bipartite graphs , play a significant role in Graph Theory, for instance, through the notions of star chromatic number and star arboricity . We may also find important applications of star graphs in Computer Science. For example, in Distributed Computing the star network is one of the most common computer network topologies. In 2023, Fernandes and Paulista [ 14 ] considered the monoid of all partial isometries of the star graph S_{n} . They determined the rank (i.e. the minimum size of a generating set) and the cardinality of this monoid as well as described its Green’s relations and exhibited a presentation. On the other hand, recently, the first two authors together with Dimitrova considered in [ 4 , 5 ] the partial counterparts of the monoids \mathrm{sEnd}(S_{n}) , \mathrm{swEnd}(S_{n}) , \mathrm{End}(S_{n}) and \mathrm{wEnd}(S_{n}) , studying their regularity, describing their Green’s relations and computing their cardinalities and ranks. In this paper, our main aim is to determine presentations for the monoids \mathrm{End}S_{n} , \mathrm{swEnd}S_{n} and \mathrm{wEnd}S_{n} , which we will carry out in Section 3 . In the first section, we will look at some basic concepts and results about presentations. In Section 2 , we describe the monoids \mathrm{Aut}S_{n} , \mathrm{sEnd}S_{n} , \mathrm{End}S_{n} , \mathrm{swEnd}S_{n} and \mathrm{wEnd}S_{n} , and recall some of their unpublished properties, namely cardinalities, regularity, generators and ranks, which were studied by the first author together with his undergraduate students Duarte Grilo and Samuel Medalha within the Undergraduate Research Opportunity Program of NOVA School of Science and Technology. For the sake of completeness, we present here brief proofs of these results. For general background on Semigroup Theory and standard notations, we would like to refer the reader to Howie’s book [ 19 ] . Regarding Algebraic Graph Theory, we refer to Knauer’s book [ 22 ] . We would also like to point out that we made use of computational tools, namely GAP [ 16 ] . 1 On presentations Let X be a set and denote by X^{*} the free monoid generated by X . Often, in this context, the set X is called an alphabet and its elements are called words . A monoid presentation is an ordered pair \langle X\mid R\rangle , where X is an alphabet and R is a subset of X^{*}\times X^{*} . An element (u,v) of X^{*}\times X^{*} is called a relation of X^{*} and it is usually represented by u=v . A monoid M is said to be defined by a presentation \langle X\mid R\rangle if M is isomorphic to X^{*}/{\sim_{R}} , where \sim_{R} denotes the congruence on X^{*} generated by R , i.e. \sim_{R} is the smallest congruence on X^{*} containing R . Suppose that X is a generating set of a monoid M and let u=v be a relation of X^{*} . We say that a relation u=v of X^{*} is satisfied by X if u=v is an equality in M . For more details, see [ 24 ] or [ 29 ] . A well-known direct method to obtain a presentation for a monoid, that we might consider folklore, is given by the following result; see, for example, [ 29 , Proposition 1.2.3] . Proposition 1.1 . Let M be a monoid generated by a set X . Then, \langle X\mid R\rangle is a presentation for M if and only if the following two conditions are satisfied: 1. The generating set X of M satisfies all the relations from R ; 2. If w_{1},w_{2}\in X^{*} are any two words such that the generating set X of M satisfies the relation w_{1}=w_{2} , then w_{1}\sim_{R}w_{2} . For finite monoids, a standard method to find a presentation is described by the following result, adapted for the monoid case from [ 29 , Proposition 3.2.2] . Theorem 1.2 (Guess and Prove method) . Let M be a finite monoid, let X be

Read the complete text