4
$\begingroup$

I did Google search and can't find a good answer. I thought I should ask experts here.

Cayley graph is defined for groups. My question is:

Is there a special name for the Cayley graph of semigroups?

  • 0
    Not as far as I know. The few times that I have seen this come up, people refer to it as the Cayley graph of the semigroup.2012-02-25

4 Answers 4

9

We call them Cayley graphs (it doesn't seem to be usual to say 'Cayley digraph'), and they are interesting. I am doing research on semigroups, and quite often draw the Cayley graph of a semigroup to get an idea of what it's like. I don't know how much background on semigroups you have, but one reason Cayley graphs for semigroups are interesting is that the $\mathcal{R}$-classes in a semigroup correspond to the strongly connected components in its (right) Cayley graph.

4

If you want to have a group theory approach, then you are right. These graphs are not interesting! However if you have a semigroup background and you know about automaton and semiautomaton, you can find these graphs very interesting (see Kilp and Knauer's book). So the second answer is not very correct and fair since the identity and inverse elements are not very good in semigroups because they make everything very similar to groups.


I completely accept that inverse semigroups (or much better, Clifford semigroups which are the semilattice of groups) are very interesting and important, and I never claim that they are not good. I told they are very similar to groups and exactly for this reason, the behavior of these Cayley graphs and required techniques are similar to the Cayley graphs of groups (but not exactly the same). However when you work with semigroups which are too far from groups (like bands), the behavior and the required techniques are very interesting because most of the time, they are not available in Group Theory and this causes a value for the independent study of Cayley graphs of semigroups and a difference between Cayley graphs of groups and semigroups.

For Tara B: Based on where you study, I think that R. Gray's works must be interesting for you and it can show you some other applications and importance of Cayley graphs of semigroups. Also I strongly suggest you to see " Generalized Cayley graphs of semigroups" in Semigroup Forum.

  • 0
    @Behnam/user64269: I only saw the bit at the end addressed to me completely by chance! I would indeed like to read some of Bob Gray's papers sometime. I have always enjoyed his talks at conferences.2013-03-11
3

You can consider every semiautomaton as an S-act, when S is a monoid.

http://books.google.com/books?id=4gPhmmW-EGcC&q=semiautomata#v=snippet&q=semiautomata&f=false

(Kilp and Knauer's book, on Page 45) So the answer of your question can be found in the same book on Page 104.

http://books.google.com/books?id=4gPhmmW-EGcC&q=product#v=snippet&q=product&f=false

Good luck

  • 0
    @TaraB Sorry I am not very good in computer and I just use it with lowest knowledge. I try to fix it again.2013-03-12
-2

The difference between a semigroup and a group is the existence of an identity and inverses and it are just those properties that make Cayley graphs interesting ( read: possible ). There are no Cayley graphs for semigroups.

  • 6
    To be fair, one may still speak of Cayley digraphs, and these may also be interesting. While your answer is strictly speaking correct, if you adopt the usual convention that graphs are undirected, it's a little uncharitable.2012-02-25