The Rado graph admits only one oligomorphic action of its automorphism group

Let R denote the Rado graph and \aut R its automorphism group. We show that any action of \aut R on R 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 (R,c) – the Rado graph with a constant – in R 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 \aut R acts on two sets X,Y, then a function f:X\to Y is equivariant if \alpha\cdot f(x)=f(\alpha\cdot x), for every x\in X and \alpha\in\aut R. We say that X and Y are equivariantly isomorphic if there is an equivariant bijection between X and Y.

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

Theorem. If  \aut R acts on a graph G with finitely many orbits and G is isomorphic to R, then the action on V(G) is equivariantly isomorphic to the natural action on  V(R).

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

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

We will use the following standard result. For a set A\subset R, let \aut R_{(A)}\subset \aut R denote the pointwise stabiliser of A.

Lemma 0. Let \aut R act transitively on a set X of dimension  d, and let A\subset R be a  set with n elements. Then X has at most 2^{d(n+1)}\cdot 3^{d^2} orbits under the action of \aut R_{(A)}.

Proof sketch. Choose an element x\in X and let  \set{a_1,\ldots,a_d}\subset R be its least support. Let N\subset R^d be the orbit of the tuple (a_1,\ldots,a_d) in R^d under \aut R. The number of orbits of M under the action of \aut R_{(A)} is bounded by the number of orbits of N under the action of \aut R_{(A)}, which is bounded by the number of atomic types of d-tuples \bar y of elements in R with constants for each element of A, which is bounded by

    \[(n+2^n)^d \cdot 3^{d\choose 2},\]

(for each of the d elements of \bar y, choose if it is equal to one of the n elements of A in at most n ways, if it is not equal to neither, choose to which of them it is adjacent in at most 2^n ways; finally, for each pair of the d elements, choose whether they are equal, non-equal and adjacent, or neither), which is at most 2^{d(n+1)}\cdot 3^{d^2}. \square


If U\subset V(G) is a finite set of vertices of a graph G, then the neighborhod diversity of U is the size of the family

    \[\set{N^G(v)\cap U:v\in V(G)},\]

where N^G(v) denotes the neighborhood of v in G.

The following lemma follows immediately from the extension axioms.

Lemma 1.  If G is isomorphic to R, then for every subset U\subset V(G) of size n, the neighborhood diversity of U is equal to 2^n.

In the rest of the proof of the main theorem, we fix a graph G and an action of \aut R on G via automorphisms, which has finitely many orbits on V(G). In what follows,  d denotes the dimension of V(G) under the action of \aut R, and k denotes the number of orbits of this action.

Lemma 2. For all m\in\mathbb N there is a subset U\subset V(G) of size m^d and neighborhood diversity at most k\cdot 2^{d(m\cdot d+1)}\cdot 3^{d^2}.

Proof. Let v be any vertex of G of dimension d, and let \set {a_1,a_2,\ldots,a_d}\subset R be its least support. Let X\subset R^d be the orbit of the tuple \bar a=(a_1,\ldots,a_d) under the action of \aut R, let Y\subset V(G) be the orbit of v, and let  f:X\to Y be the equivariant surjective function which maps \bar a to v (the existence and uniqueness of f follows from the fact that \bar a supports d).

Let A_1,A_2,\ldots A_d\subset R be finite sets. We say that the tuple (A_1,\ldots,A_d) is \bar a-uniform if the following conditions hold for P=\prod_{i=1}^dA_i:

  1. \bar a\in P,
  2. P\subset X,
  3. The restriction of f to P is 1-1.

Clearly, the tuple (\set{a_1},\ldots,\set{a_d}) is \bar a-uniform.

We prove the following.

Claim. Let (A_1,\ldots,A_d) be \bar a-uniform and let 1\le i\le d. Then there is an element a\in R such that adding a to A_i results in a \bar a-uniform tuple (A_1,\ldots, A_i\cup\set a,\ldots A_d).

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

    \[C=\set {a\in R: \set a\times A_2\times \cdots \times A_d}\subset X}.\]

Observe that a_1\in C. Suppose that C is finite. Then by definition, it follows that a_1 is in the algebraic closure of A_2\cup\ldots \cup A_d in R. Since R has no algebraicity, it follows that a_1\in A_2\cup\ldots \cup A_d. This implies that \set{a_1}\times A_2\cdots \times A_d\subset X contains a tuple with two equal coordinates, which is a contradiction.

Hence C is infinite. Choose any element a\in C-\bigcup_{i=1}^d A_i. Clearly, the tuple (A_1\cup\set a, A_2,\ldots, A_d) satisfies the first two conditions of \bar a-uniformness. We check the last condition.

Suppose that f(\bar b)=f(\bar c), for some two tuples \bar b,\bar c\in (A_1\cup\set a) \times A_2\cdots \times A_d. To prove \bar b=\bar c, we consider three cases.

  1.  b_1\neq a and c_1\neq a. In this case, \bar b,\bar c\in\prod_{i=1}^d A_i, and therefore, \bar b=\bar c by \bar a-uniformness.
  2. Exactly one of b_1,c_1 is equal to a. By symmetry, we may assume that b_1=a. Since \bar b is the least support of f(\bar b) and \bar c is the least support of f(\bar c) and f(\bar b)=f(\bar c) by assumption, we have that a belongs to the tuple \bar c, implying that a\in \bigcup_{i=1}^d A_i, a contradiction.
  3. b_1=c_1=a. Note that a and a_1 have the same atomic types over A_2\cup\cdots \cup A_d. Hence there exists an automorphism \alpha of R which fixes A_2\cup \cdots \cup A_d and maps a to a_1. Then f(\alpha(\bar b))=\alpha\cdot f(\bar b)=\alpha\cdot f(\bar c)=f(\alpha(\bar c)), hence \alpha(\bar b)=\alpha(\bar c) since f is 1-1 on \prod_{i=1}^d A_i. This proves \bar b=\bar c.

Therefore, f is 1-1 on (A_1\cup\set a) \times A_2\times \cdots\times A_d, proving the claim.

It follows that for every m\in\Nat there is a \bar a-uniform tuple (A_1,\ldots,A_d), such that |A_i|=m for i=1,\ldots,d. Let P=\prod_{i=1}^d A_i\subset X, and let U=f(P)\subset Y\subset V(G). Note that |U|=|P|=m^d by \bar a-uniformness. To conclude the lemma, we prove that U has small neighborhood diversity.

Let A=\bigcup_{i=1}^d A_i\subset R and n=|A|; in particular, n=m\cdot d. Note that if v,w\in V(G) are in the same orbit of the action of \aut R_{(A)}, then v and w have the same neighborhoods in U. Therefore, the neighborhood diversity of U is bounded by the number of orbits of the action of \aut R_{(A)} on V(G) which, by Lemma 0, is bounded by

    \[k\times 2^{d(n+1)}\cdot 3^{d^2}\]

(where k denotes the number of orbits of the action of \aut R on V(G)). This proves Lemma 2.\square

Corollary 1. If G is isomorphic to R, then d=1.

Proof. By Lemma 1 and Lemma 2, we have

    \[k\cdot 2^{d(m\cdot d+1)}\cdot 3^{d^2}\ge 2^{m^d},\]

for every m. This can only hold if d=1. \square

Lemma 3. Suppose that d=1; let l be the number of 1-dimensional orbits of G and let f be the number of 0-dimensional orbits of G, i.e., fixpoints. Then for every n\in \mathbb N, there is a set U\subset V(G) of size l\times n whose neighborhood diversity is at most f+l\cdot 6\cdot 2^{n}.

Proof. Let n\in\mathbb N, and let A\subset R be a set of size n. Let U\subset V(G) be the set of all vertices v such that the least support of v is \set{a}, for some a\in A. Then U has exactly l\times n elements (this follows from the transitivity of the action of \aut R on R). Note that if  v,w\in V(G)  are in the same orbit of \aut R_{(A)}, then they have the same neighborhoods in U. Therefore, the neighborhood diversity of U is bounded by the number of orbits of V(G) under the action of \aut R_{(A)}. By Lemma 0,  the number of orbits of V(G) under the action of \aut R_{(A)} is bounded by f+l\cdot 3\cdot 2^{n+1}.\square

We now prove the theorem. Suppose that G is isomorphic to R. By Corollary 1, we have that d=1. By Lemma 3 and Lemma 1, we have f+l\cdot 6\cdot 2^{n}\ge 2^{l\cdot n}, for every n\in\Nat, which can only happen if l\le 1, hence there is only one  orbit Y\subset V(G) of dimension 1. In particular, V(G)-Y is finite, and consists of fixpoints of \aut R. But there can be no fixpoint, since a fixpoint would be connected to all vertices in Y or to no vertex in Y; in particular, to all but finitely many vertices of G or to at most finitely many vertices in G, which cannot happen if G is isomorphic to R. Therefore, V(G) consists of exactly one orbit of dimension 1.

Let v\in V(G), and let \set{a}\subset R be its least support. Let f:R\to V(G) be the equivariant function which maps a to v; then f is a surjection since V(G) has one orbit. Moreover, f is 1-1, since \text{ker} f is an equivariant equivalence relation on R, and R is primitive. Therefore, f is an equivariant isomorphism from V(R) to V(G), finishing the proof of the theorem. \square

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

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

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

Corollary. There is no interpretation of (R,c) in R which does not use parameters.

Proof. Neither R nor \bar R have an invariant constant.\square


Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>