Which graphs are Cayley graphs?

Question

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 $\Gamma$. 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 $\Gamma$ 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 $\Gamma$. The point of my question is that we are given only the graph $\Gamma$ 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 $\Gamma$ is a Cayley graph iff there is a subgroup $G$ of the Automorphism group of $\Gamma$ 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 $\Gamma$ 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 $\Gamma$ is a Cayley graph or not depends on the set-theoretic background? For example, perhaps $\Gamma$ 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 $\Gamma$. This cannot occur for countable graphs, since the condition of being a Cayley graph is at worst $\sum_1^1$, 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 $\Gamma$, 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 $\sum_1^1$ (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. $\Gamma$ 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 $\Gamma$, which is not a Cayley graph, but such that a group presentation can be added by forcing.

Answer 1

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 $\Gamma$ 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 $\Gamma$ 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, $\Gamma$ 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 $\Gamma$ 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 $\Gamma$ is the countable tree in which every vertex has countably infinite in-out degree. Thus, in the forcing extension, $\Gamma$ is the Cayley graph of the free group on countably many generators. $_\square$

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

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

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 $\Gamma$ that holds exactly of the finite-degree Cayley graphs. Specifically, the set of finite-degree countable Cayley graphs has complexity at most $\sum_4^0$ in the arithmetic hierarchy.

Proof. Let us suppose that the graph $\Gamma$ is given to us simply as a binary relation on $\omega$, that is, an element of $2^{\omega\times\omega}$. The assertion that the graph is connected has complexity $\prod_2^0$, 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 $\sum_4^0$, since you can say "there is a natural number $k$ such that for all vertices $v$ there are $k$ vertices $w_1,\dotsc,w_k$ pointing at $v$, such that no other vertex points at $v$ (and similarly for pointing out).

Now, suppose that $\Gamma$ is a connected directed graph and all in-out degrees are $k$. Fix a node $e$ that will represent the group identity (if $\Gamma$ 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 $\Gamma$ really is a Cayley graph, these will be the generators). Define that $p$ is a partial labeling of the edges of $\Gamma$ with generators, if $p$ is a function defined in a finite distance ball of $e$ in $\Gamma$, 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 $\Gamma$ 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 $\Gamma$, 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 $\Gamma$ and satisfies the coherence condition. Such a labeling exactly provides a group presentation with Cayley graph $\Gamma$.

The complexity of saying that every initial segment of the nodes admits a coherent labeling is $\prod_2^0$, 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 $\Delta_0^0$ requirement on $p$. $_\square$

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 $\Gamma$, 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.

Answer 2

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.

Answer 3

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 F_A (with generating set A) by interpreting each letter a of a word in F_A 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 F_A). Then Γ is the Cayley graph of the quotient F_A/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.

Answer 4

For the completeness of the answer, I would like to point out some recent results (not publish though) on this subject.

Abstract:

We show that the directed labelled Cayley graphs coincide with the rooted deterministic vertex-transitive simple graphs. The Cayley graphs are also the strongly connected deterministic simple graphs of which all vertices have the same cycle language, or just the same elementary cycle language. Under the assumption of the axiom of choice, we characterize the Cayley graphs for all group subsets as the deterministic, co-deterministic, vertex-transitive simple graphs.

Answer 5

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...

Answer 6

Here is an answer, assuming that you are able to find the automorphism group of your graph.

A simplicial graph $\Gamma$ is a (simplicial) Cayley graph if and only if it is connected and its group of graph automorphisms contains a subgroup $G$ that acts freely transitively on its vertex set.

Given such a graph $\Gamma$, such a $G$, and a choice of base vertex $v_0\in \Gamma$, the generating set $S$ is the set of all elements of $G$ that send $v_0$ to one of its neighbours. The graph $\Gamma$ is $G$-equivariantly isomorphic to the graph $\hbox{Cay}(G,S)$ with vertex set $G$ and edge set the collection of all pairs of group elements of the form $\{g,gs\}$ with $g\in G$ and $s\in S$. An isomorphism from $\hbox{Cay}(G,S)$ to $\Gamma$ is defined by sending the vertex $g$ to the vertex $gv_0$ and the edge $\{g,gs\}$ to the (unique) edge in $\Gamma$ between $gv_0$ and $gsv_0$.