Eliminating constant in Rado graph
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 .
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$:
- $\bar a\in P$,
- $P\subset X$, and
- 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$