The random graph is the Fraisse limit of the class of finite graphs, the random directed graph is the Fraisse limit of the class of directed graphs, a directed graph is just a set with a binary relation.


It's easy to see that the random directed graph interprets the random graph, in fact the second is a reduct of the first. I am curious to know about the other direction. I don't see an easy way to do it, or an easy way to rule it out. More generally, I would be curious have pointers to research on when countable homogeneous structures interpret other countable homogeneous structures. I don't know if anyone has thought about this, I'm not very familiar with that terrain.


Motivation: I am doing some work with a weak notion of interpretability. I show that the random graph weakly interprets the random directed graph, and I use this as a fairly important lemma. So I'm curious to know if anything is known/obvious to experts about actual interpretations. If there is an actual interpretation then it would be a bit silly to spend a page constructing a weak interpretation.


I am actually thinking about the random $k$-ary hypergraph and the random $k$-ary relation.



Does the random graph interpret the random directed graph?
No, the random graph cannot interpret the random binary relation.


I’ll just answer the title question with the goal of illustrating a technique; I haven't considered $k$-ary structures. The approach is to use the property of least supports to set up a counting argument. Some equivalences are discussed at [Least supports and weak elimination of imaginaries](http://atoms.mimuw.edu.pl/?p=1281). Combined with $\omega$-categoricity we get a useful classification of all definable equivalence relations. I’ll use the following result with $M$ being the random graph.



> 
> **Fact.** [1, Lemma 2.7(ii)] If $X\subseteq M^n$ is invariant, there is a unique smallest set $D\subset M$ such that $X$ is $D$-invariant.
> 
> 
> 


“$D$-invariant” means $X$ is preserved setwise by all automorphisms that fix $D$ elementwise. “Invariant” means $D\_0$-invariant for some finite $D\_0.$ Since $M$ has an $\omega$-categorical theory, invariant is the same as definable, and $D$-invariant is the same as $D$-definable. The proof in [1] uses the free amalgamation property. I’m not sure whether this special case is obvious or not.


Fix:


* a finite set $M\_0\subset M$
* an $M\_0$-definable set $X\subseteq M^n$
* an $M\_0$-definable equivalence relation ${\sim}\subseteq X\times X,$ and
* an $M\_0$-definable relation $R\subseteq X\times X$ that respects ${\sim}$ i.e. it’s the preimage of a relation $R/{\sim}\subseteq (X/{\sim})\times(X/{\sim}).$


We aim to show that $(X/{\sim}, R/{\sim})$ is not isomorphic to the random binary relation.


For each complete $n$-type $p$ over $M\_0$ let $X\_p=\{x\in X:M\Vdash p(x)\}.$ Let $P=\{p:X\_p\neq\emptyset\}.$ Pick representatives $x\_p\in X\_p$ for each $p\in P.$ Let $x\_p/{\sim}$ denote the ${\sim}$-equivalence class of $x\_p.$ By the Lemma, for each $p$ there is a unique smallest set $D$ such that $x\_p/{\sim}$ is $D$-definable. We must have $D\subset \operatorname{rng}(x\_p).$ Let $I\_p\subset \{1,\dots,n\}$ be a minimal set of indices such that $\operatorname{rng}(x|I\_p)=D$ - this step is necessary because $x\_p$ might have repeated components. Let $\hat{p}$ denote the type of $x|I\_p$ over $M\_0,$ implicitly reindexing if necessary, or allowing types to use free variables $x\_i,i\in I\_p$ instead of the usual contiguous $x\_1,\dots,x\_{|I\_p|}.$ Note that $I\_p$ and $\hat p$ do not depend on the choice of $x\_p\in X\_p.$


By uniqueness, whenever $x,y\in X\_p$ have different supports, i.e. $\operatorname{rng}(x|I\_p)\neq \operatorname{rng}(y|I\_p),$ then $x\not\sim y.$ So $x/{\sim}$ is coded by $x|I\_p$ modulo perhaps a permutation group acting on the indices of $I\_p.$


For each $p,q\in P$ define $R\_{p,q}$ on vectors $\hat{x}\in X^{I\_p}$ and $\hat{y}\in X^{I\_q}$ by


$$R\_{p,q}(\hat x,\hat y)\iff (\exists x\in X\_p)(\exists y\in X\_q)(x\supseteq \hat x \wedge y \supseteq \hat y \wedge R(x,y))$$


Then for $x\in X\_p$ and $y\in X\_q$ we have $R\_{p,q}(x|I\_p,y|I\_q)\iff R(x,y)$ because the choice of extension doesn’t affect the equivalence classes: by definition of $I\_p$ any automorphism fixing $x|I\_p$ will fix $x/{\sim},$ and similarly for $y|I\_q.$ The relation $R\_{p,q}$ is $M\_0$-definable.


Let $d=\max\_{p\in P}|I\_p|.$ If $d=0$ then $X/{\sim}$ is finite, which is absurd. The $d=1$ case could be handled by symmetry, but the following counting argument happens to cover this case too. So assume $d\geq 1.$


Pick $N$ large enough that $$4^{N^d}>|P|(N^d+2^{Nd})^d.$$


Pick $p$ with $|I\_p|=d.$ Use the extension property to pick $dN$ distinct vertices $x\_{i,j}$ where $i\in I\_p$ and $1\leq j\leq N,$ satisfying $M\Vdash \hat p((x\_{i,{j\_i}})\_{i\in I\_p})$ for each $j: I\_p\to \{1,\dots,N\}.$ In graph theory terms we’re blowing up each vertex $(x\_p)\_i$ into $N$ vertices. It doesn’t matter whether there are edges between $x\_{i,j}$ and $x\_{i,k}$ for the same $i.$


For each $q\in P$ I estimate that there are at most $(N^d+2^{Nd})^d$ types over $M\_0$ realized by tuples of the form $((x\_{i,j})\_{i\in I\_p,1\leq j\leq N},y)$ with $y\in X^{I\_q}$ and $M\Vdash \hat{q}(y).$ This is because the type of the tuple is determined by the binary relations, and the only freedom is how the $1$-type of each $y\_k$ over $M\_0$ extends to a $1$-type over $M\_0\cup \{x\_{i,j}:i\in I\_p, 1\leq j\leq N\}.$ There are at most $N^d+2^{Nd}$ such extensions: either $y\_k=x\_{i,j}$ for some $(i,j),$ or else there are the $2^{Nd}$ choices of whether or not each $\{x\_{i,j},y\_k\}$ is an edge.


Each $y\in X$ determines values $z\_y(j)\in \{1,2,3,4\}$ for each $j: I\_p\to \{1,\dots,N\},$ according to whether $R\_{p,q}(x\_{i,j\_i},y)$ and $R\_{q,p}(y,x\_{i,j\_i})$ are false/false, false/true, true/false or true/true. By the estimate in the previous paragraph, there are at most $|P|(N^d+2^{Nd})^d$ distinct functions of the form $z\_y.$ So there is some $z\in 4^{N^{I\_p}}$ not equal to $z\_y$ for any $y.$ In terms of the original interpretation, we can pick $\xi^j\in X\_p$ with $\xi^j\_i=x\_{i,j\_i}.$ The equivalence classes $\xi^j/{\sim}$ are distinct because they have different supports. The extension property for the random binary relation requires that there exists $y\in X$ such that $R(\xi^j, y)$ and $R(y,\xi^j)$ are false/false etc according to $z(j).$ But then $z=z\_y,$ contradicting the choice of $z.$


[1] *Macpherson, Dugald; Tent, Katrin*, [**Simplicity of some automorphism groups.**](http://dx.doi.org/10.1016/j.jalgebra.2011.05.021), J. Algebra 342, No. 1, 40-52 (2011). [ZBL1244.20002](https://zbmath.org/?q=an:1244.20002).


