Rado graph containing infinitely many isomorphic subgraphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:23:20Z http://mathoverflow.net/feeds/question/18475 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18475/rado-graph-containing-infinitely-many-isomorphic-subgraphs Rado graph containing infinitely many isomorphic subgraphs Hans Stricker 2010-03-17T10:26:41Z 2013-02-27T12:33:15Z <p>The Rado graph contains every finite graph as an induced subgraph. It surely contains <em>some</em> finite graphs infinitely often as an induced subgraph, e.g. $K_2$. Does it contain <em>all</em> finite graphs infinitely often as an induced subgraph? Or can an example of a graph be given that is <em>not</em> contained infinitely often?</p> http://mathoverflow.net/questions/18475/rado-graph-containing-infinitely-many-isomorphic-subgraphs/18476#18476 Answer by Robin Chapman for Rado graph containing infinitely many isomorphic subgraphs Robin Chapman 2010-03-17T10:40:32Z 2010-03-17T10:40:32Z <p>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$.</p> <p>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.</p> http://mathoverflow.net/questions/18475/rado-graph-containing-infinitely-many-isomorphic-subgraphs/121911#121911 Answer by Yann Peresse for Rado graph containing infinitely many isomorphic subgraphs Yann Peresse 2013-02-15T15:52:50Z 2013-02-27T12:33:15Z <p>I realise that the question is almost three years old, but maybe that's not that long in Maths. </p> <p>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.</p> <p>Let $G=G_0$ be any countable graph. For $i>0$ define a new Graph $G_i$ as follows: </p> <ul> <li><p>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})$.</p></li> <li><p>All edges of $V(G_{i-1})$ are also edges of $V(G_{i})$</p></li> <li><p>Add an edge between $a\in V(G_{i-1})$ and $v_{A}\in V(G_{i})$ whenever $a\in A$.</p></li> </ul> <p>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$.</p> <p>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.</p>