Is the Rado graph a Cayley graph? If so, what is the group like? (And other questions...)

Question

The countable random graph, also known as the Rado graph, is characterized as the unique countable graph in which every two disjoint finite sets $A$ and $B$ of vertices admit a vertex $p$ connected to every vertex in $A$ and to none in $B$. This is a kind of saturation property, and any two countable graphs exhibiting it are isomorphic by a fun back-and-forth construction; indeed, any finite partial isomorphism extends in this situation to a full isomorphism. The same argument shows that every countable graph has many copies inside the Rado graph. The Rado graph can also be described as the almost-sure result of constructing an edge between any two distinct integers with independent probability $p\in(0,1)$, essentially because the probability of fulfilling the property for any two $A$ and $B$ is one, since there are infinitely many independent chances to get the pattern correct. (Note, in this question, graphs have no trivial loops or parallel edges.)

My questions are:

• Is the Rado graph a Cayley graph? That is, can one orient and label the edges with generators in such a way that the Rado graph is the resulting Cayley graph of the corresponding group presentation? (I expect that the answer is yes, by building up a simply transitive group action and employing Sabidussi's theorem, but I would be interested to see an elegant account of this idea if it works.)

• If so, is the resulting group unique? What is its nature?

• For example, can one make the Rado graph a Cayley graph of a group with torsion? without torsion?

• Does the group exhibit a probabilistic account, as the graph does?

• If the Rado graph is a Cayley graph, what universal properties does the resulting group enjoy similar to the attractive universal properties of the graph? For example, every countable Cayley graph finds a copy in the Rado graph; can we always find a copy whose Cayley labeling extends to a Cayley labeling of the full Rado graph?

It seems that the ideas of the random graph extend in several ways to the context of directed graphs. For example, one could ask that for every disjoint triple of sets $A$, $B$ and $C$, there is a node $p$ pointing at all nodes in $A$, pointed at by all nodes in $B$ and with no edges between $p$ and nodes in $C$. This saturation property again characterizes the directed graph up to isomorphism by a back-and-forth construction. I suppose this graph would also be the almost-sure result of building the Rado graph probabalistically, but also orienting the edges with independent probability $p$.

• Are any of the questions above affected by this change? That is, in this version of the questions, the edge orientations are already given, but satisfy the saturation property.

• And what of the uncountable analogues of the random graph? For example, if the Continuum Hypothesis holds, then there is a (unique) graph of size $\aleph_1$ satisfying the saturation property with respect to all countable disjoint subsets $A$, $B$, that is, having a vertex connected to all vertices in $A$ and to none in $B$. Is this graph a Cayley graph, and so on?

Answer 1

For the question of whether the Rado graph is the Cayley graph of any group see "An essay on countable B-groups" by Cameron-Johnson. They prove

Let $G$ be a countable group which cannot be expressed as a finite union of translates of non-principal square-root sets and a finite set. Then the set of Cayley graphs for $G$ which are isomorphic to $R$ is residual.

(A non-principal square-root set is the set of all elements in the group which square to a specific non-identity element.)

There are many groups satisfying the conditions of the theorem. You might also be interested in Cameron's "Homogeneous Cayley objects" where he treats the problem of deciding which countable groups can act regularly on countable homogeneous relational structures.

Answer 2

To answer your question about having a probabilistic account: it seems like it should work easily enough just to use $(\mathbb{Z},+)$ as the group, with $\pm i$ belonging to the set of generators with probability $1/2$, independently for each $i$. Then, just as in the Erdős–Rényi random graph construction, for any A and B one has infinitely many independent chances of finding a vertex adjacent to all of A and none of B.

This construction of an infinite random circulant graph is described by Zhang and Huang, "Infinite circulants and their properties", Acta Math. Appl. Sinica 1995, but they don't mention any connection to the Rado graph.

Answer 3

The answer that I started to write is a combination of Gjergji's answer and David's answer. Let $G$ be a countable group which is not a finite union of translates of non-principal square root sets and a finite set. Then as David says, you get infinitely many independent chances to find $p$. As in Joel's original set-up, you can also use biased coin tosses to make the edges.

I'm left wondering when a countably infinite group is a finite union of translates of non-principal square root sets and a finite set. I guess that $C_2^{\infty} \times A$ is an example, if $A$ is a finite group which is not an elementary 2-group. Certainly no elementary $p$-group (or, additively, no vector space over $\mathbb{Z}/p$) is an example, and neither is $\mathbb{Z}^n$. And I guess that $\text{SL}(n,\mathbb{Z})$ isn't an example either.

---

There are two different kinds of directed graphs, graphs with and without 2-cycles. The question posed considers the kind without 2-cycles, but I don't see a problem defining either kind of Rado graph on the same class of groups. For that matter, you could have various kinds of colored Rado graphs, where some of the edge colors are directed and others are undirected. (So, allowing 2-cycles amounts to having two undirected colors and one directed color.)

I don't think that it really says a whole lot about the group. It says that the Rado graph has such a huge automorphism group that many groups act freely transitively on it. It looks like the Cameron-Johnson condition on the group $G$ is actually not only sufficient for a freely transitive action, but also necessary, at least to obtain the $n$-colored Rado graph for every finite $n$ as a Cayley graph of $G$. Still, the groups $G$ that are impossible are essentially impossible for a local reason.

As for the uncountable analogues of the random graph, I might guess that the same constructions still work sometimes, but I would ask someone like Joel Hamkins. :-)