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, 2013 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, 2013 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$
    – Nobody
    Apr 22, 2013 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, 2013 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, 2013 at 10:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.