Tag Archives: random graph

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.

Continue reading

Least supports and non-interpretability

In this post, we give a proof that (\str Q,\le) does not interpret (without parameters) in the homogeneous poset P nor in the random graph R. The idea is to first show that every continuous action of \aut P  or \aut R on a set is faithful or trivial. We show this by using the fact that P and R have least supports. Since \aut P and \aut R have an automorphism of order two and \aut {\str Q,\le} does not, this proves that there is no nontrivial continuous action of \aut P nor \aut R on \str Q.

Continue reading