1
$\begingroup$

The Rado graph is universal since it contains an isomorphic copy of every countable graph (infinitely often). The Rado graph can be explicitely constructed and an isomorphic copy of any countable graph can be effectively computed.

Is there also a universal directed graph, especially one with an explicit construction?

1 Answers 1

1

Yes. Use the same construction as the Rado graph, but replace the base 2 by base 4. The vertices are in one-to-one correspondence with the natural numbers, with edges obeying the following rule.

For any two vertices $x,y$ with $x:

  1. If the $x$th bit of the base-4 expansion of $y$ is a $0$, then there are no edges between $x$ and $y$.

  2. If the $x$th bit of the base-4 expansion of $y$ is a $1$, then there is a directed edge from $x$ to $y$.

  3. If the $x$th bit of the base-4 expansion of $y$ is a $2$, then there is a directed edge from $y$ to $x$.

  4. If the $x$th bit of the base-4 expansion of $y$ is a $3$, then there are directed edges in both directions between $x$ and $y$.

This has very similar properties to the Rado graph, and roughly the same algorithm works for finding induced subgraphs of a given isomorphism type.

Incidentally, the idea here is presumably the same as the construction of 4-edge-colored Rado graph $G_4$ mentioned in "related concepts" section of the same Wikipedia article.

  • 0
    @Hans: I would recommend looking up references on the 4-edge-colored Rado graph, e.g. the reference to Truss (1985) mentioned in the article. A directed graph really isn't very different from the type of 4-edge-colored graph they are considering.2011-06-06