Lengths of words in transformation semigroups generated by digraphs

DOI10.1007/S10801-016-0703-9MaRDI QIDQ510064zbMATH OpenOpenAlexWikidataFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 16 February 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3627463 (Why is no real title available?)
• A classification of the maximal idempotent-generated subsemigroups of finite singular 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.
• Maximal regular subsemibands of \(\text{Sing}_n\).
• On Subtournaments of a Tournament
• Products of idempotents in finite full transformation semigroups
• The Maximum Number of Strongly Connected Subtournaments^*
• The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup

Cited in

(10)

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

Describes a project that uses

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)