Lengths of words in transformation semigroups generated by digraphs
Lengths of words in transformation semigroups generated by digraphs
复制标题
DOI：
10.1007/s10801-016-0703-9
复制
发表时间：
2016-02
影响因子：
0.8
通讯作者：
P. Cameron;Alonso Castillo-Ramirez;M. Gadouleau;J. D. Mitchell
中科院分区：
文献类型：
--
作者：
P. Cameron;Alonso Castillo-Ramirez;M. Gadouleau;J. D. Mitchell
给定一个简单的digraphDonnvertices (with)，有一个变换半群的自然构造。对于d的任意边（a,b），设秩映射带固定除a以外的所有顶点的幂等性；然后，定义为由for all生成的半群。对于，让一个单词的最小长度i (D)表示。众所周知，所有秩变换的半群最多是由秩的幂等产生的。当得到完整的无向图时，Howie和Iwahori分别得到了一个公式来计算任意；然而，没有类似的非平凡的结果是已知的。在本文中，我们刻画了所有的简单有向图，使得它们要么等于Howie-Iwahori的公式，要么等于所有，要么等于所有。我们还得到了endi是无环有向图或强竞赛时的界（后一种情况对应于rankof的最小幂等生成集）。我们以一系列猜想和未解决的问题来结束论文。
Given a simple digraphDonnvertices (with), there is a natural construction of a semigroup of transformations. For any edge (a,b) ofD, letbe the idempotent of rankmappingatoband fixing all vertices other thana; then, defineto be the semigroup generated byfor all. For, letbe the minimal length of a word inE(D) expressing. It is well known that the semigroupof all transformations of rank at mostis generated by its idempotents of rank. Whenis the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate, for any; however, no analogous non-trivial results are known when. In this paper, we characterise all simple digraphsDsuch that eitheris equal to Howie–Iwahori’s formula for all, orfor all, orfor all. We also obtain bounds forwhenDis an acyclic digraph or a strong tournament (the latter case corresponds to a smallest generating set of idempotents of rankof). We finish the paper with a list of conjectures and open problems.