Eliminating constant in Rado graph

Question

Let $R$ denote the Rado graph, and let $c$ be a fixed vertex.

Question 1. Is the structure obtained by extending $R$ by the constant $c$ interpretable in $R$ without parameters?

By interpretable I mean first-order interpretable; see below for an equivalent formalism.

A related group-theoretic question is the following. Let $\text{Aut}(R)$ denote the group of automorphisms of the Rado graph.

Question 2. Is there an action of $\text{Aut}(R)$ on $R$ by automorphisms fixing $c$ which has finitely many orbits?

---

Edit (11 Oct'16):

Here's a purely group-theoretic weakening of Question 2:

Question 2'. Is the group $\text{Aut}(R)$ isomorphic to a subgroup of $\text{Aut}(R,c)$, the group of automorphisms of $R$ fixing $c$?

Edit: Question 2' has been answered positively by 'Rado the explorator' below. Unfortunately, this still doesn't answer Questions 1 and 2, since the induced action has infinitely many orbits.

---

Here is some background to this question, and some minor observations.

For a relational structure $\mathbb A$ and its element $c$, let $(\mathbb A,c)$ denote the structure obtained from $\mathbb A$ by adding the constant $c$. If $\mathbb A$ has the property that for every constant $c$, $(\mathbb A,c)$ interprets without constants in $\mathbb A$, then let us say that $\mathbb A$ has elimination of parameters. Equivalently, this means that any relational structure $S$ which interprets in $R$ with parameters also interprets in $S$ without parameters.

In a comment to this question: ω-categorical, ω-stable structure with trivial geometry not definable in the pure set I remarked that $(\mathbb N,=)$ has elimination of parameters, and stated that this holds for any $\omega$-categorical structure, but Alex Kruckman pointed to an error in my reasoning, but we figured out a proof for $(\mathbb N,=)$. Here is an even simpler proof.

Fact. $(\mathbb N,=)$ has elimination of parameters.

In the proof, I allow myself to use a more convenient syntax for defining interpretations in a structure $\mathbb A$, which I call definable sets. The syntax of sets definable over $\mathbb A$ allows using set-builder expressions with variables ranging $\mathbb A$, and which can be constrained using first-order formulas in the language of $\mathbb A$; additionally, we can take finite unions or tuples of such expressions, and nest these operations. For instance, the set $\{(x,y):x,y\in\mathbb N, x\neq y\}\cup\{x:x\in\mathbb N, x\neq 5\}\cup \{\{x,y\}:x,y\in\mathbb N\}$ is definable over $(\mathbb N,=)$, using the parameter $5$. A relational structure $\mathbb B=(B,R_1,\ldots,R_n)$ is definable over $\mathbb A$ if $B$ and each relation $R_i$ is a set which is definable over $\mathbb A$. Up to isomorphism, structures definable over $\mathbb A$ are the same as structures which interpret in $\mathbb A$, using first-order interpretations (this correspondence preserves the used parameters), but sometimes using definable sets makes constructions easier, as e.g. below. When the definition does not involve parameters, we say that the structure is 0-definable.

Proof. We show that $(\mathbb N,=,c)$ is isomorphic to a structure which is definable over $(\mathbb N,=)$: Indeed, the structure $(\mathbb N\cup\{\emptyset\},R_=,c)$, where $c$ is the constant interpreted as $\emptyset\in\mathbb N\cup\{\emptyset\}$ and $R_==\{(m,m):m\in\mathbb N\}\cup\{(\emptyset,\emptyset)\}$ is clearly 0-definable over $(\mathbb N,=)$ and isomorphic to $(\mathbb N,=)$. (It is also easy to construct a two-dimensional interpretation in $(\mathbb N,=)$ without parameters). $\square$

Fact. $(\mathbb Q,\le)$ has elimination of parameters.

Proof. Here the construction is slightly more interesting. A constant $c\in\mathbb Q$ splits $\mathbb Q$ into two parts: the rationals smaller than $c$ and the rationals larger than $c$, and the interaction between the two parts is very simple. The structure $(\mathbb Q,\le, c)$ is isomorphic to the following structure. It's domain is $X=\{(q,L):q\in\mathbb Q\}\cup\{(q,R):q\in\mathbb Q\}\cup\{C\}$, where $L,R,C$ are symbols, e.g. implemented as $\emptyset,\{\emptyset\},\{\{\emptyset\}\}$ which are 0-definable, and so is $X$. We now define the relation $\le$ on $X$ by $R_\le=\Big\{((q,L),(q',L)):q,q'\in \mathbb Q, q<q'\Big\}\cup \Big\{((q,R),(q',R)):q,q'\in \mathbb Q, q<q'\Big\}$$ $$\cup \Big\{((q,L),(q',R)):q,q'\in \mathbb Q\Big\}\cup \Big\{((q,L),C):q\in \mathbb Q\Big\}\cup \Big\{(C,(q,R)):q\in \mathbb Q\Big\}$,

which is also clearly 0-definable over $(\mathbb Q,\le)$. Finally, $(\mathbb Q,\le,c)$ is isomorphic to $(X,R_\le,C)$.$\square$

The question of this post is the following.

Question 1. Does the Rado graph $R$ have elimination of parameters?

Observe that a constant $c$ in $R$ splits the Rado graph into two parts: the neighbors $A$ of $c$ and the non-neighbors $B$. Each part is isomorphic to the Rado graph, and the interaction between the two parts is like a random bipartite graph. The structure $(R,A,B)$ is isomorphic to a random graph with a random partition. Question 1 is therefore equivalent to the question whether the random graph with a random partition interprets in $R$ without parameters.

Another question is the following.

Question 3. Which $\omega$-categorical structures have elimination of parameters?

In group-theoretic terms, if a structure $\mathbb A$ 0-interprets in $R$, then the group of automorphisms of $R$ acts continuously on $\mathbb A$, and this action is oligomorphic, i.e., it induces finitely many orbits on $\mathbb A$, on $\mathbb A^2$, on $\mathbb A^3$, etc. In particular, if $(R,c)$ interprets in $R$, then there is an action of $\text{Aut}(R)$ on $(R,c)$ by automorphisms, which has finitely many orbits. Question 2 asks whether such an action exists? (Continuity of this action follows from the fact that $\text{Aut}(R)$ has the small index property. Also, if the action has finitely many orbits on $R$, then it is oligomorphic).

Answer 1

Question 2' has a positive answer: for any countably infinite graph $\mathcal{G}$, there exists an embedding of $\mathcal{G}$ in the Rado graph so that the automorphisms of $\mathcal{G}$ extend uniquely. This is a theorem of Henson from the late sixties and the proof is not hard. Now just apply this, starting with $\mathcal{G}$ equal to the Rado graph plus a vertex connected to every point.

I don't think that this says anything about your question 2 since there will be infinitely many orbits for this embedding .

Answer 2

The answer to questions 1 and 2 is negative. Here is a proof. It is based on discussions I had in 2016 with Marcello Mamino, Antoine Mottet, Manuel Bodirsky, and others at TU Dresden.

$\newcommand{\aut}[1]{\textrm{Aut}(#1)}$ $\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\Nat}{\mathbb N}$ $\renewcommand{\subset}{\subseteq}$

---

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.

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 (this follows e.g. from weak elimination of imaginaries and no algebraicity, or the condition in Theorem 9.3 in this paper https://arxiv.org/pdf/1402.0897v2.pdf). 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$, and
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$