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
:
,
,
- 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.
-
and
. In this case,
, and therefore,
by
-uniformness.
- 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.
. 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.