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.