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$ :

$\bar a\in P$ ,
$P\subset X$ ,
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.

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

Atompress

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

Leave a Reply Cancel reply

Computation with atoms