I am trying to track down the name of this digraph and some references:

You take all members of the transformation semigroup on $n$ elements, $T_{n}$.

For two members $x$ ,$y$ ; if $x$ is in the semigroup generated by y then you put an arrow from $y$ -> $x$ . You would read this as "$x$ is in the semigroup generated by $y$". Alternatively $y^k = x$.

What is the name of this digraph? References would be great.

If you wanted to visualize it, the symmetric group $S_{n}$ would be one of the connected components. The sinks are idemptent transformations like (0,1,2,3), (1,1,1,1), ...

  • $\begingroup$ Just found this article. Digraphs and the semigroup of all functions on a finite set, by Peter M. Higgins, Glasgow J. Math. 30 (1988), pp. 41-57 $\endgroup$ Apr 19 '13 at 19:58
  • $\begingroup$ This article isn't what I am looking for as the transformations are the vertices in my digraph, not the elements 0...n-1 as in this paper. $\endgroup$ Apr 19 '13 at 20:06
  • $\begingroup$ I asked a question Cayley graph of semigroups on Math SE. I hope it would be somewhat helpful to you. $\endgroup$
    – scaaahu
    Apr 22 '13 at 10:03
  • $\begingroup$ I've never heard of this digraph before, sorry. It's quite a strange object. Sure, $S_n$ is a connected component, but the only strongly connected components are the cyclic subgroups. How did you come across this, and can you give me a reason to believe it's somehow a useful way of viewing $T_n$, or interesting for some other reason? $\endgroup$
    – Tara B
    Apr 25 '13 at 10:33
  • 1
    $\begingroup$ Ah, sorry, I only just saw this, because I wasn't notified of your reply. What do you mean exactly by the 'Green relation digraphs'? (The left and right Cayley graphs of a semigroup give you all the information about ${\cal R}$ and ${\cal L}$, but I haven't seen digraphs for the other Green's relations.) $\endgroup$
    – Tara B
    Apr 26 '13 at 10:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.