Given any digraph without loops or multiple arcs, there is a natural construction of a semigroup of transformations. To every arc of is associated the idempotent transformation mapping to and fixing all vertices other than . The semigroup is generated by the idempotent transformations for all arcs of .
In this paper, we consider the question of when there is a transformation in containing a large cycle, and, for fixed , we give a linear time algorithm to verify if contains a transformation with a cycle of length . We also classify those digraphs such that has one of the following properties: inverse, completely regular, commutative, simple, 0-simple, a semilattice, a rectangular band, congruence-free, is -trivial or -universal where is any of Green’s -, -, -, or -relation, and when has a left, right, or two-sided zero.
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.56
Keywords: digraphs, flow semigroup of digraph, semigroups, monoids
East, James 1; Gadouleau, Maximilien 2; Mitchell, James D. 3
@article{ALCO_2019__2_5_711_0, author = {East, James and Gadouleau, Maximilien and Mitchell, James D.}, title = {Structural aspects of semigroups based on digraphs}, journal = {Algebraic Combinatorics}, pages = {711--733}, publisher = {MathOA foundation}, volume = {2}, number = {5}, year = {2019}, doi = {10.5802/alco.56}, zbl = {07115038}, mrnumber = {4023563}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.56/} }
TY - JOUR AU - East, James AU - Gadouleau, Maximilien AU - Mitchell, James D. TI - Structural aspects of semigroups based on digraphs JO - Algebraic Combinatorics PY - 2019 SP - 711 EP - 733 VL - 2 IS - 5 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.56/ DO - 10.5802/alco.56 LA - en ID - ALCO_2019__2_5_711_0 ER -
%0 Journal Article %A East, James %A Gadouleau, Maximilien %A Mitchell, James D. %T Structural aspects of semigroups based on digraphs %J Algebraic Combinatorics %D 2019 %P 711-733 %V 2 %N 5 %I MathOA foundation %U https://alco.centre-mersenne.org/articles/10.5802/alco.56/ %R 10.5802/alco.56 %G en %F ALCO_2019__2_5_711_0
East, James; Gadouleau, Maximilien; Mitchell, James D. Structural aspects of semigroups based on digraphs. Algebraic Combinatorics, Volume 2 (2019) no. 5, pp. 711-733. doi : 10.5802/alco.56. https://alco.centre-mersenne.org/articles/10.5802/alco.56/
[1] The defining relations of the endomorphism semigroup of a finite linearly ordered set, Sib. Mat. Zh., Volume 3 (1962), pp. 161-169 | MR | Zbl
[2] Digraphs, Springer Monographs in Mathematics, Springer London, 2009 | DOI | Zbl
[3] Bounds of the number of leaves of spanning trees, Journal of Mathematical Sciences, Volume 184 (2012) no. 5, pp. 564-572 | DOI | MR | Zbl
[4] Graph Theory, Graduate Texts in Mathematics, Springer, 2008
[5] Lengths of words in transformation semigroups generated by digraphs, Journal of Algebraic Combinatorics, Volume 45 (2017) no. 1, pp. 149-170 | DOI | MR | Zbl
[6] Idempotent Generation in the Endomorphism Monoid of a Uniform Partition, Communications in Algebra, Volume 44 (2016) no. 12, pp. 5179-5198 | DOI | MR | Zbl
[7] Classical Finite Transformation Semigroups, Algebra and Applications, 9, Springer London, 2009 | DOI | MR | Zbl
[8] On the ranks of certain finite semigroups of transformations, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 101 (1987) no. 3, pp. 395-403 | DOI | MR | Zbl
[9] Combinatorial results for semigroups of order-preserving mappings, Mathematical Proceedings of the Cambridge Philosophical Society, Volume 113 (1993) no. 2, pp. 281-296 | DOI | MR | Zbl
[10] Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, Volume 16 (1973) no. 6, pp. 372-378 | DOI
[11] The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs, International Journal of Algebra and Computation, Volume 27 (2017) no. 7, pp. 863-886 | DOI | MR | Zbl
[12] The subsemigroup generated by the idempotents of a full transformation semigroup, J. London Math. Soc., Volume 41 (1966) no. 1, pp. 707-716 | DOI | MR | Zbl
[13] Idempotent generators in finite full transformation semigroups, Proceedings of the Royal Society of Edinburgh: Section A Mathematics, Volume 81 (1978) no. 3-4, pp. 317-323 | DOI | MR | Zbl
[14] Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, 12, The Clarendon Press Oxford University Press, New York, 1995, x+351 pages (Oxford Science Publications) | MR | Zbl
[15] The disjoint paths problem in quadratic time, Journal of Combinatorial Theory, Series B, Volume 102 (2012) no. 2, pp. 424-435 | DOI | MR | Zbl
[16] Coordinating Pebble Motion On Graphs, The Diameter Of Permutation Groups, And Applications, 25th Annual Symposium on Foundations of Computer Science, 1984. (1984), pp. 241-250 | DOI
[17] et al. Semigroups - GAP package, Version 3.1.1 (2019) | DOI
[18] Varieties of Formal Languages, Foundations of Computer Science, Springer, 1986
[19] The ()-puzzle and related relocation problems, Journal of Symbolic Computation, Volume 10 (1990) no. 2, pp. 111-137 | DOI | MR | Zbl
[20] Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy, and Games, World Scientific Pub Co Inc, 2009
[21] Catalan monoids, monoids of local endomorphisms, and their presentations, Semigroup Forum, Volume 53 (1996) no. 1, pp. 351-368 | DOI | MR | Zbl
[22] GAP – Groups, Algorithms, and Programming, Version 4.10.1 (2019) (https://www.gap-system.org)
[23] Graph puzzles, homotopy, and the alternating group, Journal of Combinatorial Theory, Series B, Volume 16 (1974) no. 1, pp. 86-96 | DOI | MR | Zbl
[24] The number of irreducible tournaments, Glasgow Mathematical Journal, Volume 11 (1970) no. 2, pp. 97-101 | DOI | MR | Zbl
[25] Maximal Regular Subsemibands of , Semigroup Forum, Volume 72 (2005) no. 1, pp. 75-93 | DOI | MR | Zbl
[26] Isomorphisms of transformation semigroups associated with simple digraphs, Asian-European Journal of Mathematics, Volume 2 (2009) no. 4, pp. 727-737 | DOI | MR | Zbl
Cited by Sources: