Lengths of words in transformation semigroups generated by digraphs

DOI10.1007/S10801-016-0703-9zbMATH Open1355.05116arXiv1602.00935OpenAlexW2255155235WikidataQ59615296 ScholiaQ59615296MaRDI QIDQ510064FDOQ510064

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 16 February 2017

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

Abstract: Given a simple digraph $D$ on $n$ vertices (with $nge2$), there is a natural construction of a semigroup $langleDangle$ associated with $D$. For any edge $(a,b)$ of $D$, let $aob$ be the idempotent of defect $1$ mapping $a$ to $b$ and fixing all vertices other than $a$; then define $langleDangle$ to be the semigroup $langleaob:(a,b)inE(D)angle$. For $alphainlangleDangle$, let $ell(D,alpha)$ be the minimal length of a word in $E(D)$ expressing $alpha$. When $D=K_n$ is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate $ell(K_n,alpha)$, for any $alphainlangle{K}_{n}angle=ext{Sing}_n$; however, no analogous nontrivial results are known when $Deq{K}_n$. In this paper, we characterise all simple digraphs $D$ such that either $ell(D,alpha)$ is equal to Howie-Iwahori's formula for all $alphainlangleDangle$, or $ell(D,alpha)=n-extfix(alpha)$ for all $alphainlangleDangle$, or $ell(D,alpha)=n-extrk(alpha)$ for all $alphainlangleDangle$. When $D$ is an acyclic digraph and $alphainlangleDangle$, we find a tight upper bound for $ell(D,alpha)$. Finally, we study the case when $D$ is a strong tournament (which corresponds to a smallest generating set of idempotents of defect $1$ of $ext{Sing}_n$), and we propose some conjectures.

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

Recommendations

• Structural aspects of semigroups based on digraphs
• Transformation semigroups generated by semicomplete digraphs
• Some remarks of finite full transformation semigroups
• Isomorphisms of transformation semigroups associated with simple digraphs.
• Products of idempotents in finite full transformation semigroups

zbMATH Keywords

word lengthtransformation semigroupsimple 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)

Cites Work

• The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup
• On Subtournaments of a Tournament
• Title not available (Why is that?)
• Products of idempotents in finite full transformation semigroups
• Catalan monoids, monoids of local endomorphisms, and their presentations
• Idempotent generators in finite full transformation semigroups
• Isomorphisms of transformation semigroups associated with simple digraphs.
• A classification of the maximal idempotent-generated subsemigroups of finite singular semigroups
• Maximal regular subsemibands of \(\text{Sing}_n\).
• The Maximum Number of Strongly Connected Subtournaments^*

Cited In (10)

• A five-element transformation monoid on labelled trees
• Structural aspects of semigroups based on digraphs
• Preset distinguishing sequences and diameter of transformation semigroups
• Isomorphisms of transformation semigroups associated with simple digraphs.
• Transformation semigroups generated by semicomplete digraphs
• Inverse monoids of partial graph automorphisms
• The maximal subgroups and the complexity of the flow semigroup of finite (di)graphs
• Lower bounds on words separation: are there short identities in transformation semigroups?
• ℋ-Trivial Transformation Semibands and Digraphs
• Completely distinguishable automata and the set of synchronizing words

Uses Software

• GAP
• Semigroups

This page was built for publication: Lengths of words in transformation semigroups generated by digraphs

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