Rado graph containing infinitely many isomorphic subgraphs - MathOverflow

Rado graph containing infinitely many isomorphic subgraphs

2010-03-17T10:26:41Z

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?

Answer by Robin Chapman for Rado graph containing infinitely many isomorphic subgraphs

2010-03-17T10:40:32Z

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.

Answer by Yann Peresse for Rado graph containing infinitely many isomorphic subgraphs

2013-02-15T15:52:50Z

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.