Let denote the Rado graph and its automorphism group. We show that any action of  on  by automorphisms which has finitely many orbits is isomorphic to the natural action. Therefore, in a sense, every interpretation of the Rado graph in itself without parameters is trivial. The proof uses a counting argument. As a corollary, every interpretation of the Rado graph in itself without parameters is definably isomorphic or anti-isomorphic to the Rado graph. Also, there is no interpretation of – the Rado graph with a constant – in which does not use parameters.

This post is based on discussions with Manuel Bodirsky, Marcello Mamino, Antoine Mottet, and others at TU Dresden.

Recall that if acts on two sets , then a function is equivariant if , for every and . We say that and are equivariantly isomorphic if there is an equivariant bijection between and .

When we speak of the group acting on a graph , we mean an action on (the vertex set of ) by automorphisms of , i.e., one which is induced by a homomorphism . There is an obvious “natural” action of on the graph ; this action has one orbit.

Theorem. If   acts on a graph  with finitely many orbits and is isomorphic to , then the action on is equivariantly isomorphic to the natural action on  .

The rest of this post is devoted to a proof of the above theorem. We begin with defining some auxiliary notions.

Since has the small index property, every action on a countable set is continuous, i.e., for every there is a finite set called a support of   such that for every automorphism , if fixes pointwise then fixes . Moreover, every has a least (under inclusion) support (see e.g. this post). If  acts continuously on a set , then we say that the dimension of an element is the  size of the least support of . The dimension of a set is the maximal dimension of any element . Observe that if are in the same orbit of the action, then they have the same dimension.

We will use the following standard result. For a set , let denote the pointwise stabiliser of .

Lemma 0. Let act transitively on a set of dimension  , and let be a  set with elements. Then has at most  orbits under the action of .

Proof sketch. Choose an element and let  be its least support. Let be the orbit of the tuple in under . The number of orbits of under the action of is bounded by the number of orbits of under the action of , which is bounded by the number of atomic types of -tuples of elements in with constants for each element of , which is bounded by (for each of the elements of , choose if it is equal to one of the elements of in at most ways, if it is not equal to neither, choose to which of them it is adjacent in at most ways; finally, for each pair of the elements, choose whether they are equal, non-equal and adjacent, or neither), which is at most .

 

If is a finite set of vertices of a graph , then the neighborhod diversity of is the size of the family

where denotes the neighborhood of in .

The following lemma follows immediately from the extension axioms.

Lemma 1.  If is isomorphic to , then for every subset of size , the neighborhood diversity of is equal to .

In the rest of the proof of the main theorem, we fix a graph and an action of on via automorphisms, which has finitely many orbits on . In what follows,   denotes the dimension of under the action of , and denotes the number of orbits of this action.

Lemma 2. For all  there is a subset  of size and neighborhood diversity at most .

Proof. Let be any vertex of of dimension , and let be its least support. Let be the orbit of the tuple under the action of , let be the orbit of , and let   be the equivariant surjective function which maps to (the existence and uniqueness of follows from the fact that supports ).

Let be finite sets. We say that the tuple is -uniform if the following conditions hold for :

1. ,
2. ,
3. The restriction of to  is 1-1.

Clearly, the tuple is -uniform.

We prove the following.

Claim. Let be -uniform and let . Then there is an element such that adding to  results in a -uniform tuple .

To simplify notation, we prove the claim for ; the general case is analogous. Let

Observe that . Suppose that  is finite. Then by definition, it follows that is in the algebraic closure of in . Since  has no algebraicity, it follows that . This implies that contains a tuple with two equal coordinates, which is a contradiction.

Hence is infinite. Choose any element . Clearly, the tuple satisfies the first two conditions of -uniformness. We check the last condition.

Suppose that , for some two tuples . To prove , we consider three cases.

1.   and . In this case, , and therefore, by -uniformness.
2. Exactly one of is equal to . By symmetry, we may assume that . Since  is the least support of and is the least support of  and  by assumption, we have that belongs to the tuple , implying that , a contradiction.
3. . Note that and have the same atomic types over . Hence there exists an automorphism of which fixes and maps to . Then , hence since is 1-1 on . This proves .

Therefore, is 1-1 on , proving the claim.

It follows that for every there is a -uniform tuple , such that for . Let , and let . Note that by -uniformness. To conclude the lemma, we prove that has small neighborhood diversity.

Let and ; in particular, . Note that if are in the same orbit of the action of , then and have the same neighborhoods in . Therefore, the neighborhood diversity of is bounded by the number of orbits of the action of on which, by Lemma 0, is bounded by (where  denotes the number of orbits of the action of on ). This proves Lemma 2.

Corollary 1. If is isomorphic to , then .

Proof. By Lemma 1 and Lemma 2, we have for every . This can only hold if .

Lemma 3. Suppose that ; let be the number of 1-dimensional orbits of and let be the number of -dimensional orbits of , i.e., fixpoints. Then for every , there is a set of size  whose neighborhood diversity is at most .

Proof. Let , and let be a set of size . Let be the set of all vertices such that the least support of is , for some . Then has exactly elements (this follows from the transitivity of the action of on ). Note that if    are in the same orbit of , then they have the same neighborhoods in . Therefore, the neighborhood diversity of is bounded by the number of orbits of under the action of . By Lemma 0,  the number of orbits of under the action of is bounded by .

We now prove the theorem. Suppose that is isomorphic to . By Corollary 1, we have that . By Lemma 3 and Lemma 1, we have , for every , which can only happen if , hence there is only one  orbit  of dimension 1. In particular, is finite, and consists of fixpoints of . But there can be no fixpoint, since a fixpoint would be connected to all vertices in or to no vertex in ; in particular, to all but finitely many vertices of  or to at most finitely many vertices in , which cannot happen if is isomorphic to . Therefore, consists of exactly one orbit of dimension .

Let , and let be its least support. Let be the equivariant function which maps to ; then is a surjection since has one orbit. Moreover, is 1-1, since is an equivariant equivalence relation on , and is primitive. Therefore, is an equivariant isomorphism from  to , finishing the proof of the theorem.

Let denote the Rado graph with edges replaced by non-edges, and vice-versa. It is easy to check that and are the only one-dimensional interpretations of the Rado graph in itself, without parameters.

Corollary. Let be a graph which interprets in the Rado graph without parameters. If is isomorphic to the Rado graph, then there is a definable isomorphism between  and  or between and .

(A definable isomorphism between two structures  which interpret in is an isomorphism such that the two-sorted structure interprets in ).

Corollary. There is no interpretation of in which does not use parameters.

Proof. Neither nor have an invariant constant.