Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Rado graph contains every finite graph as an induced subgraph. It surely contains some finite graphs infinitely often as an induced subgraph, e.g. $K_2$. Does it contain all finite graphs infinitely often as an induced subgraph? Or can an example of a graph be given that is not contained infinitely often?

share|improve this question

2 Answers 2

up vote 9 down vote accepted

It must contain every finite subgraph infinitely often as an induced subgraph. For a finite graph $G$ and the positive integer $n$ consider the graph $H$ consisting of $n$ vertex-disjoint copies of $G$. As $H$ is an induced subgraph of Rado then there are $n$ vertex-disjoint induced subgraphs of Rado isomorphic to $G$.

According to Wikipedia, Rado also has every countable graph as an induced subgraph (I wasn't aware of this until now). Then the above argument will work for countable graphs too.

share|improve this answer
    
My god, things are so simple sometimes. Thanks! –  Hans Stricker Mar 17 '10 at 10:55
    
Sometimes simple things can be hard to see :-) –  Robin Chapman Mar 17 '10 at 21:02

I realise that the question is almost three years old, but maybe that's not that long in Maths.

I am not sure who the following is originally due to, but as far as I am aware, it's the standard to show that the Rado graph contains every countable graph. The idea is to start with whatever graph you want and construct the Rado graph around it.

Let $G=G_0$ be any countable graph. For $i>0$ define a new Graph $G_i$ as follows:

  • The vertices $V(G_{i})$ of $G_i$ are all of $V(G_{i-1})$ plus an extra vertex $v_A$ for every finite subset $A$ of $V(G_{i-1})$.

  • All edges of $V(G_{i-1})$ are also edges of $V(G_{i})$

  • Add an edge between $a\in V(G_{i-1})$ and $v_{A}\in V(G_{i})$ whenever $a\in A$.

Let $R$ be the union of the graphs $G_i$ over all $i>0$. Then show that $R$ is the Rado graph. Clearly, $R$ contains $G=G_0$.

One of the nice things about this construction is that you can show without much difficulty that any automorphism of $G$ extends to an automorphism of $R$. So not only does the Rado graph contain every countable graph $G$, but it contains "special" copies of $G$ with the above extension property.

share|improve this answer

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.