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

8

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
    Thanks for the info of Kilp and Knauer's book. I did not know that book. However, I am not that interested in wreath product. Do you happen to know some info about direct product of semiautomata? Thanks again.2013-02-28
  • 2
    I don't agree that inverse elements are 'not very good in semigroups'. Inverse semigroups (semigroups in which every element has a unique inverse) are interesting semigroups which are still quite far from being groups.2013-03-02
  • 2
    @Benham: You can merge your current account with the one you used to post this answer originally by doing this: `From any page footer -> 'contact us' >> 'Merge user profiles'`2013-03-02
  • 0
    @ZevChonoles: Sorry I rolled back the edit because I thought it was a different user...2013-03-02
  • 0
    @Thomas: No worries, that's completely understandable. I've rolled back the rollback :)2013-03-02
  • 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
    Thank you. I am not sure if you and user64269 are the same person. Thanks to both of you. I'll get the book.2013-03-02
  • 0
    Sorry, I should have verified my e-mail address before.2013-03-02
  • 1
    You can flag the moderator to merge your two accounts into one.2013-03-02
  • 1
    @Behnam: This doesn't appear to be an answer to the question about Cayley graphs. (It's not really a problem in this case, but generally 'answers' should be answers to the question they are posted as answers to.) It would probably have been better to add this to your original answer, as it was the answer to a question asked by scaahu in response to that answer.2013-03-02
  • 0
    You are right but I am not very familiar with this site. I try to fix it.2013-03-02
  • 0
    I can not add comment to the above post so I answer here.2013-03-02
  • 0
    @Tara B: Cayley graphs and semiautomaton are not very different (see Page 45 of Kilp and Knauer's book). Also if you assume that the connection set C in Cayley graph to be a subsemigroup of S, the Cayley graph Cay(S,C) and S as a C-act are closely related to each other.2013-03-02
  • 0
    @Behnam: Well, that's the sort of information you should put in your answer, to explain how your answer is related to the question.2013-03-11
  • 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