Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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<y$:

  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.

share|improve this answer
    
Thanks. Do you have a reference where I can learn a little bit more about the directed Rado graph? –  Hans Stricker Jun 6 '11 at 7:14
    
@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. –  Jim Belk Jun 6 '11 at 7:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.