# Which graphs are Cayley graphs?

Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.

My main question is, suppose that we are given a directed graph Γ. How can we tell if it is the Cayley graph of some group presentation?

Clearly, certain finistic properties are required: it should be connected; every vertex must have the same in and out degrees; and moreover, the automorphism group of the graph must be vertex transitive, since the left action of the group G on the Cayley graph is vertex transitive. In particular, all the local neighborhoods of every vertex must be isomorphic.

I am aware of Sabidussi's theorem, which states that a graph Γ is a Cayley graph of a group G if and only if it admits a simply transitive action of G by graph automorphisms (simply transitive = exactly one element of G acts to move a given vertex v to another w). But this theorem does not answer my question, since it presumes that we already have the group G and the action of G on Γ. The point of my question is that we are given only the graph Γ and seek a graph-theoretic condition telling us whether or not there is a group G satisfying the Sabidussi condition. (In particular, I won't be impressed by an answer stating that Γ is a Cayley graph iff there is a subgroup G of the Automorphism group of Γ satisfying the Sabidussi condition.)

There are other natural related questions.

• Are there non-Cayley graphs, such that all finite subgraphs are (induced) subgraphs of a Cayley graph? In other words, this question is asking whether the collection of Cayley graphs is not a closed set in the space of all graphs.

• Is there a computable graph Γ which is the Cayley graph of a group presentation, but which is not the Cayley graph of any computable group presentation? Here, by a computable graph I mean a graph whose vertices are the natural numbers, and whose edge relation is a computable relation. In the finite degree case, one may build the tree-of-attempts to find a labeling of the graph. This tree is computable, infinite and finitely branching, so by the Low Basis theorem it will have a low branch. Thus, every computable graph that is a Cayley graph has a labeling that is low (in particular, strictly below the halting problem).

• Is it possible that the question of whether a given graph Γ is a Cayley graph or not depends on the set-theoretic background? For example, perhaps Γ is not a Cayley graph in one model of set theory V, but there is a forcing extension V[G] in which there is a group having Cayley graph Γ. This cannot occur for countable graphs, since the condition of being a Cayley graph is at worst Σ11, but in the general case, it is an intriguing possibility. (And I have confused myself several times now about this.)

Let me clarify the kind of answer I am looking for in my main question.

• On the affirmative side, I secretly hope that there is a completely finitistic graph condition, which if satisfied, would mean that the graph could be labeled and become a Cayley graph. Ideally, this finitistic condition should involve quantifying only over the finite subgraphs of Γ, and not involve computing any infinite objects. This would be great! Perhaps there is such a condition for the finite degree case?

• On the negative side, I wonder that there may be no such finitistic condition. One strategy for proving this would be to show that the collection of countable Cayley graphs is not arithmetically definable. Perhaps it is not even a Borel set. Indeed, it may even be a complete Σ11 (complete analytic) set. This would imply that any condition holding of all and only the countable Cayley graphs must involve an existential quantifier over countable objects (e.g. Γ is Cayley iff there is a labeling of it making it a Cayley graph).

• Another strategy for proving a weaker version of such a negative result would be to show that there are computable graphs, which are Cayley graphs, but which have no computable labeling to make them a Cayley graph. This would show that the connection between the graph and the group action cannot be so tight.

• Another attack on the negative side would be to show that the set-theoretic dependence actually occurs. What would be needed is a crazy graph Γ, which is not a Cayley graph, but such that a group presentation can be added by forcing.

-
The main question is purely group-theoretic, but I added the logic tags because of the additional questions. –  Joel David Hamkins Feb 9 '10 at 23:14
One comment on the non-directed case: Every connected regular graph of even degree is a Schreier coset graph. This isn't quite a Cayley graph but a natural generalization of one, so I thought you might find this interesting. –  Alon Amit Feb 10 '10 at 0:13
@JDH: I'm sorry for my (now deleted) answer. I didn't mean to be obnoxious; I simply didn't read your question through the fourth paragraph! Your question seems like such a natural one of the variant answered by Sabidussi's theorem that it must either have a known answer or be a famous open problem. I'll try to find out which is the case. –  Pete L. Clark Feb 10 '10 at 2:37
Pete: No problem! And I'll look forward to whatever you come up with. It doesn't seem so clear to me how to find the group action just from the graph. It isn't unique, after all, since I think that different groups can have the same Cayley graph, if you forget the labels. Perhaps it would be helpful for someone to post an answer explaining at least that fact... –  Joel David Hamkins Feb 10 '10 at 2:41
Joel, you're right that they may not be unique. Look at David Epstein's answer to mathoverflow.net/questions/14696/… –  HJRW Feb 10 '10 at 2:47

I've managed to answer a few of the latter questions, and please look below for a solution in the finite-degree case.

Theorem. There is an uncountable graph Γ that is not a Cayley graph in the set-theoretic universe V, but which is a Cayley graph in a larger set-theoretic universe, obtained by forcing.

Proof. Let Γ be a directed graph that is a tree, such that all vertices have infinite in-out degree, but such that some of these degrees are countable and some uncountable. For example, perhaps all the in-degrees are countable and all out-degrees are uncountable. It is not difficult to construct such a graph. Clearly, Γ cannot be a Cayley graph, since the degrees don't match. Denote the (current) set-theoretic universe by V, and perform forcing to a forcing extension V[G] in which Γ is countable. (It is a remarkable fact about forcing that any set at all can become countable in a forcing extension.) In the extension V[G], the graph Γ is the countable tree in which every vertex has countably infinite in-out degree. Thus, in the forcing extension, Γ is the Cayley graph of the free group on countably many generators.QED

Theorem. There is a graph Γ, which is not a Cayley graph, but every finite subgraph of Γ is part of a Cayley graph. Indeed, every countable subgraph of Γ is part of a Cayley graph. Every countable subgraph of Γ can be extended to a larger countable subgraph of Γ that is a Cayley graph.

Proof. The same graph Γ as above works. Every countable subgraph of Γ involves only countably many edges, and can be placed into a countable subgraph of Γ that is the Cayley graph of the free group on countably many generators. QED

The conclusion is that you cannot tell if an uncountable graph is a Cayley graph by looking only at the finite subgraphs, or indeed, by looking only at its countable subgraphs.

These observations show that in the uncountable case, one should just restrict the question at the outset to graphs satisfying the degree-matching condition.

Let me also give the fuller details for the finite-degree case, following the suggestion of François Dorais (and my tree-of-attempts argument).

Theorem. There is a finitistic condition on countable graphs Γ that holds exactly of the finite-degree Cayley graphs. Specifically, the set of finite-degree countable Cayley graphs has complexity at most Σ04 in the arithmetic hierarchy.

Proof. Let us suppose that the graph Γ is given to us simply as a binary relation on ω, that is, an element of 2ωxω. The assertion that the graph is connected has complexity Π02, since you must only say that every two vertices are connected by a finite path. The assertion that the graph has finite degree and all in-out degrees are the same has complexity Σ04, since you can say "there is a natural number k such that for all vertices v there are k vertices w1,...,wk pointing at v, such that no other vertex points at v (and similarly for pointing out).

Now, suppose that Γ is a connected directed graph and all in-out degrees are k. Fix a node e that will represent the group identity (if Γ is a Cayley graph, any node will do since they all look the same, so take e=0). Let us refer to the k nodes pointed at from e as the set of generators (since if Γ really is a Cayley graph, these will be the generators). Define that p is a partial labeling of the edges of Γ with generators, if p is a function defined in a finite distance ball of e in Γ, where p labels each arrow in that ball with a generator. Such a labeling is coherent if first, for every node every generator is used once going out from that node and once going into that node, and second, if for every node v, if there is a loop starting and ending at v, then the word w obtained from that loop works as a loop from every node to itself. We only enforce the requirements on coherence of p as far as p is defined (since it is merely a partial function). Thus, a coherent labeling is an attempt to make a labeling of the the graph into a Cayley graph, that has not run into trouble yet.

Let T be the collection of finite coherent labelings, labeling all edges on the first n nodes for some n. This is a finitely branching tree under inclusion.

I claim that Γ is a Cayley graph if and only if there are arbitrarily such large coherent labelings. The forward direction is clear, since we may restrict a full coherent labeling to any finite subgraph. Conversely, if we can find a coherent labeling for any finite subgraph of Γ, then the tree T is infinite and finitely branching. Thus, by Konig's lemma there is an infinite branch. Such a branch labels all the edges in Γ and satisfies the coherence condition. Such a labeling exactly provides a group presentation with Cayley graph Γ.

The complexity of saying that every initial segment of the nodes admits a coherent labeling is Π02, since you must say for every n, there is a labeling p of the first n nodes such that p is coherent. Being coherent is a Δ00 requirement on p. QED

In particular, to recognize when a graph is a finitely generated Cayley graph does not require one to quantify over infinite objects, and so for finite degree graphs, this is an answer to the main question.

I was surprised that the part of the description driving the complexity is the assertion that the degrees must all match, rather than the assertion that there are coherent labelings on the finite subgraphs. Can this be simplified?

This still leaves the case of countably many generators wide open. Also, this still doesn't answer the question about having a computable graph Γ, which is a Cayley graph, but which has no computable presentation. Such an example would be very interesting. Even in the finite degree case, as I mentioned in the question, the best the argument above produces is a low branch.

-
I guess this degree-matching requirement can be simplified to Sigma^0_3. You just say: there is k such that 0 points at k vertices and for any k+1 many arrows, they don't point all at the same vertex, and whenever k vertices point at v and w is a vertex, then there are k arrows pointing at w (and silarly for out-degree). This makes the condition Sigma^0_3 altogether. –  Joel David Hamkins Feb 12 '10 at 14:48
Side note: The way the equal degree condition makes the complexity go up one notch may seem unusual, but this is actually very common. Another example of this happens with König's Lemma. It is true that every infinite recursive subtree of $2^{<\omega}$ has a low branch, but this is not true that every infinite recursive subtree of $\omega^{<\omega}$ where each node has at most two successors. Indeed, there is such a recursive subtree of $\omega^{<\omega}$ where every branch computes the jump! The reason is essentially the same, you first need to find a bound on the successors of a node... –  François G. Dorais Feb 12 '10 at 14:50
... in order to tell when the node has 0, 1, or 2 successors. The same happens here. If you have an effective bound on the neighbors of each vertex, then the equal degree condition becomes much simpler. –  François G. Dorais Feb 12 '10 at 14:52
Thanks very much, François! Now, let's figure out the countably generated case. I am thinking it may be complete Sigma^1_1, which would be a negative answer, in the sense that it would mean that the easiest way to say a countable graph Gamma is a Cayley graph is to say that there is a group presentation for which it is the Cayley graph. –  Joel David Hamkins Feb 12 '10 at 15:10
My usual approach to proving Sigma^1_1 completeness is to first find a good ordinal rank on the complement so I can get a good handle. There are some candidates (involving trees of approximations of the sequence E_i that I described in another comment) but, so far, they all seem difficult to play with... –  François G. Dorais Feb 12 '10 at 15:25

I hope this not too tangential to count as an "answer" -- as Tullia Dymarz explained to me the other day, there are infinite regular (finite-degree) graphs which are not only not Cayley graphs, but are not even quasi-isometric to a Cayley graph! See the paper of Eskin, Fisher, and Whyte:

http://arxiv.org/abs/math.GR/0607207

for examples. So there may be obstructions to being quasi-isometric to a Cayley graph which can be added to your list of necessary properties above.

-
Thanks very much for this; it's quite interesting. –  Joel David Hamkins Feb 22 '10 at 0:36

In my interpretation of your directions, this is not an acceptable answer to your main question, but I think it's sufficiently different from what you wrote to warrant mention. It might also spark some better answers and/or give a better handle for the followup questions.

The directed graph Γ = (V,E) is a Cayley graph if and only if it is connected and the edge set is the union of the graphs of a family of A permutations of V that generate a group G whose nontrivial elements have no fixed points. (And Γ is, up to isomorphism, the Cayley graph of G for the set of generators A.)

Note that any two distinct permutations a, b in the family A must have disjoint graphs, otherwise the nontrivial element ab-1 of G would have a fixed point. Therefore, the family A can be viewed as a labeling of the edges of Γ, as in your tree argument at the end.

Another way to interpret this labeling is as follows. For each a ∈ A, every vertex of V has precisely one incoming edge and one outgoing edge with label a. We can use this labeling to construct an action of the free group FA (with generating set A) by interpreting each letter a of a word in FA as "follow the outgoing edge labeled a" and its inverse a-1 as "follow the incoming edge labeled a." This action is isomorphic to the action of a group on itself if and only if (1) the action is transitive and (2) all vertices have the same stabilizer R (which must therefore be a normal subgroup of FA). Then Γ is the Cayley graph of the quotient FA/R, with generating set induced by A.

Of course, this is exactly the labeling you used for your tree argument at the end, but I think it's worth spelling these things out in detail.

-

From wikipedia we have : "The Bethe lattice where each node is joined to 2n others is essentially the Cayley graph of a free group on n generators." So solution for Your question, at least for a groups with finite number of generators, may be something likethat:

Graph V is a Cayley Graph for some group G if there exists graph B and equivalence relation of vertexes K such that:

1. Graph B is Bethe lattice and has vertexes of order 2n ( every vertex is connected to 2n edges)
2. V is isomorphic to B under K ( equivalence relation glues together vertexes.)

Relation to finite presentation of group and to free group seems to be natural here. The question is what if group has to have infinite number of generators. Of course I leave to You nontrivial part of proof ;-) which I do not know ;-) but I suppose relation between Bethe Latices and Cayley graphs seems to be central here because it is effective.

Note after Joel Comment:

Suppose we order edges which emanating from certain vertex. So we assign numbers 1, to first chosen edge, 2 to the second one and so on up to 2n for the last one. Then every edge emanating from certain vertex will have its number. As in Bethe lattice every vertex has the same structure of edges, we may propagate this way of ordering between all vertices, so every vertex has the same numbering. Then I believe that proper requirement we should set on our relation K is that it should state something only about finite ( or infinite in case of infinite generated group) sequence of edges, gluing only vertices for which sequence of edges is in relation. For example every vertexes connected by sequence (1,2,3) has to be glued ( what may describe situation that generators $g_1,g_2,g_3$ has to obey $g_1g_2g_3 = id$ relation ). Then this kind of relation is "global" in that meaning that it acts in the same way on every vertex. Probably it may be stated in more formal way:

1a. given is ordering system for edges emanating from every vertex

1b. relation K states only about vertexes connected by finite ( or infinite) sequences of edges ( which probably may be stated by requirement that relation K uses only edge sequences and not names of vertices)

Motivation: As regards to complexity: every finite presented ( or infinite presented I presume) group has infinite way of presentation, and also every group has relation K for which G=F/K where F is free group. For every group G You may set K to be equal the kernel of the group, that is a set of elements which are equal to identity. Of course they may be one or several optimal or simple ways of presenting of group by means of some kind of usability criteria, and usually K stated pure formally is far from being optimal. And I agree, it is stated in very extravagant way. I suppose that a question which require some "minimal relation K" for Bethe lattice here would be much harder to express. When there would be some kind of effective criteria on minimality, probably they may be used in theory of presentation of groups, so they would be far from triviality, as this kind of problems, as far as I know, have not effective solution... But of course it would be much more interesting, whilst my way is probably near trivial...

-
Not every quotient graph of the Bethe lattice by an equivalence relation is a Cayley graph. For example, if you identify exactly two nodes, it will still be mostly a tree, with one loop, and this cannot be a Cayley graph, since in a Cayley graph, all nodes are isomorphic. Also, your characterization has complexity Sigma^1_1, because you quantify over the infinite object of the equivalence relation, whereas in the finite degree case we already found a Sigma^0_3 property, which is much lower in the complexity hierarchy. –  Joel David Hamkins Feb 21 '10 at 14:45
You I right, I obviously missed point. So probably relation K should be king of "global relation" and not for particular vertexes, as Cayley graph is always self similar, although not always infinite... –  kakaz Feb 21 '10 at 18:21
Joel, may I ask You for comment on this question: mathoverflow.net/questions/15835/…. Forgive me if it is a trouble for You, and that I am asking for that here, but I would like to have some clear opinion on that question. Of course if it is too much work to elaborate on that, because for example, I completely say something messy, just say it is stupid in short, and I will rethink it. Thanks a lot! Kazimierz Kurz. –  kakaz Feb 21 '10 at 18:59
Your revised version is much better, but it is now looking increasingly like the condition we arrived at in the finitely branching case in my answer, we were consider the possibility of having coherent labelings of the edges of more and more of the graph. Finally, Kakaz, I'm sorry, but I found I didn't have anything to add to your new question that I didn't already say in your previous two questions on that topic. –  Joel David Hamkins Feb 22 '10 at 1:59
Yes, it seems that question of labelling is somehow internally connected to this question, probably it is the key property. Thank You for note on my new question. –  kakaz Feb 22 '10 at 8:46