Structural aspects of semigroups based on digraphs

DOI10.5802/ALCO.56MaRDI QIDQ2328130zbMATH OpenOpenAlexWikidataFDO

Authors James East, Maximilien Gadouleau, J. D. Mitchell

Publication date 9 October 2019

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1704.00937

zbMATH Keywords

digraphssemigroupsmonoidsflow semigroup of digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Semigroups of transformations, relations, partitions, etc. (20M20)

Abstract: Given any digraph $D$ without loops or multiple arcs, there is a natural construction of a semigroup $langleDangle$ of transformations. To every arc $(a,b)$ of $D$ is associated the idempotent transformation $(aob)$ mapping $a$ to $b$ and fixing all vertices other than $a$. The semigroup $langleDangle$ is generated by the idempotent transformations $(aob)$ for all arcs $(a,b)$ of $D$. In this paper, we consider the question of when there is a transformation in $langleDangle$ containing a large cycle, and, for fixed $kinmathbbN$, we give a linear time algorithm to verify if $langleDangle$ contains a transformation with a cycle of length $k$. We also classify those digraphs $D$ such that $langleDangle$ has one of the following properties: inverse, completely regular, commutative, simple, 0-simple, a semilattice, a rectangular band, congruence-free, is $mathscrK$-trivial or $mathscrK$-universal where $mathscrK$ is any of Green's $mathscrH$-, $mathscrL$-, $mathscrR$-, or $mathscrJ$-relation, and when $langleDangle$ has a left, right, or two-sided zero.

Recommendations

• Transformation semigroups generated by semicomplete digraphs
• Lengths of words in transformation semigroups generated by digraphs
• Isomorphisms of transformation semigroups associated with simple digraphs.
• ℋ-Trivial Transformation Semibands and Digraphs
• Automorphisms of endomorphism semigroups of reflexive digraphs

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 3185028 (Why is no real title available?)
• Bounds of the number of leaves of spanning trees
• Catalan monoids, monoids of local endomorphisms, and their presentations
• Classical finite transformation semigroups. An introduction.
• Combinatorial results for semigroups of order-preserving mappings
• Digraphs
• Graph puzzles, homotopy, and the alternating group
• Idempotent generation in the endomorphism monoid of a uniform partition
• Idempotent generators in finite full transformation semigroups
• Isomorphisms of transformation semigroups associated with simple digraphs.
• Lengths of words in transformation semigroups generated by digraphs
• Maximal regular subsemibands of \(\text{Sing}_n\).
• On the ranks of certain finite semigroups of transformations
• The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The disjoint paths problem in quadratic time
• The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs
• The number of irreducible tournaments

Cited in

(11)

• Digraph of the full transformation semigroup
• scientific article; zbMATH DE number 2102749 (Why is no real title available?)
• Isomorphisms of transformation semigroups associated with simple digraphs.
• Transformation semigroups generated by semicomplete digraphs
• Action graph of a semigroup act & its functorial connection
• Optimisation via encodings: a renormalisation group perspective
• The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs
• Subsemigroup of \(T_n\) assigned to a fixed point free permutation
• ℋ-Trivial Transformation Semibands and Digraphs
• Lengths of words in transformation semigroups generated by digraphs
• Green's symmetries in finite digraphs

Describes a project that uses

Uses Software

• Algorithm 447
• Semigroups
• GAP

This page was built for publication: Structural aspects of semigroups based on digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2328130)