Structural aspects of semigroups based on digraphs

East, James; Gadouleau, Maximilien; Mitchell, James D.

doi:10.5802/alco.56

East, James ¹; Gadouleau, Maximilien ²; Mitchell, James D.³

¹ Centre for Research in Mathematics School of Computing Engineering and Mathematics Western Sydney University Locked Bag 1797, Penrith NSW 2751, Australia.
² Department of Computer Science Durham University South Road, Durham DH1 3LE, UK.
³ School of Mathematics and Statistics University of St Andrews St Andrews, Fife KY16 9SS, UK.

Algebraic Combinatorics, Volume 2 (2019) no. 5, pp. 711-733.

Abstract

Given any digraph $D$ without loops or multiple arcs, there is a natural construction of a semigroup $〈 D 〉$ of transformations. To every arc $(a, b)$ of $D$ is associated the idempotent transformation $(a \to b)$ mapping $a$ to $b$ and fixing all vertices other than $a$ . The semigroup $〈 D 〉$ is generated by the idempotent transformations $(a \to b)$ for all arcs $(a, b)$ of $D$ .

In this paper, we consider the question of when there is a transformation in $〈 D 〉$ containing a large cycle, and, for fixed $k \in ℕ$ , we give a linear time algorithm to verify if $〈 D 〉$ contains a transformation with a cycle of length $k$ . We also classify those digraphs $D$ such that $〈 D 〉$ 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 $〈 D 〉$ has a left, right, or two-sided zero.

Received: 2018-03-02
Revised: 2018-11-26
Accepted: 2018-12-21
Published online: 2019-10-08

MR Zbl

DOI: 10.5802/alco.56

Classification: 20M20, 05C20, 05C25
Keywords: digraphs, flow semigroup of digraph, semigroups, monoids

Author's affiliations:

East, James ¹; Gadouleau, Maximilien ²; Mitchell, James D. ³

¹ Centre for Research in Mathematics School of Computing Engineering and Mathematics Western Sydney University Locked Bag 1797, Penrith NSW 2751, Australia.
² Department of Computer Science Durham University South Road, Durham DH1 3LE, UK.
³ School of Mathematics and Statistics University of St Andrews St Andrews, Fife KY16 9SS, UK.

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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/

References
Cited by

[1] Aĭzenshtat, A. Ya. 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] Bang-Jensen, Jørgen; Gutin, Gregory Z. Digraphs, Springer Monographs in Mathematics, Springer London, 2009 | DOI | Zbl

[3] Bankevich, A. V.; Karpov, Dmitriy V. 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] Bondy, Adrian Graph Theory, Graduate Texts in Mathematics, Springer, 2008

[5] Cameron, P. J.; Castillo-Ramirez, A.; Gadouleau, M.; Mitchell, J. D. 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] Dolinka, Igor; East, James 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] Ganyushkin, Olexandr; Mazorchuk, Volodymyr Classical Finite Transformation Semigroups, Algebra and Applications, 9, Springer London, 2009 | DOI | MR | Zbl

[8] Gomes, Gracinda M. S.; Howie, John M. 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] Higgins, Peter M. 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] Hopcroft, John; Tarjan, Robert Algorithm 447: efficient algorithms for graph manipulation, Communications of the ACM, Volume 16 (1973) no. 6, pp. 372-378 | DOI

[11] Horváth, Gábor; Nehaniv, Chrystopher L.; Podoski, Károly 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] Howie, John M. 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] Howie, John M. 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] Howie, John M. 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] Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce 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] Kornhauser, Daniel; Miller, Gary; Spirakis, Paul 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] Mitchell, James D. et al. Semigroups - GAP package, Version 3.1.1 (2019) | DOI

[18] Pin, Jean Eric Varieties of Formal Languages, Foundations of Computer Science, Springer, 1986

[19] Ratner, Daniel; Warmuth, Manfred The ( $n^{2} - 1$ )-puzzle and related relocation problems, Journal of Symbolic Computation, Volume 10 (1990) no. 2, pp. 111-137 | DOI | MR | Zbl

[20] Rhodes, John 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] Solomon, Andrew 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] Wilson, Richard M. 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] Wright, E. M. The number of irreducible tournaments, Glasgow Mathematical Journal, Volume 11 (1970) no. 2, pp. 97-101 | DOI | MR | Zbl

[25] Yang, Xiuliang; Yang, Haobo Maximal Regular Subsemibands of ${Sing}_{n}$ , Semigroup Forum, Volume 72 (2005) no. 1, pp. 75-93 | DOI | MR | Zbl

[26] Yang, Xiuliang; Yang, Haobo 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: