0

As part of Theorem 2.6 Bollobas gives an example of a unique graph up to isomorphism for a countable vertex random graph with $P_k$ for each k (i.e. extension axiom) : $G_0$ = ($\mathbb{N}$,E) with E ={ij : i < j, $p_i$ | j}. Presumably this is the same as the Rado graph, which is isomorphic to the hereditary finite sets, with vertices interpreted as finite sets, with no sets duplicated. However $G_0$ appears to contain an infinite number of duplicates of each finite set. So for example vertex 1 appears as the only vertex connected to (i.e. as the only element in) vertex numbers 2, 4, 8, 16,...since vertex 1 is associated with the prime number 2 and vertex number 2^k is only ever divided by 2.

So is this correct - countable random graphs can contain an infinite number of duplicates of each set, and if so how does Theorem 2.6 get around this? (The proof of Theorem 2.6 appears to assume there are no duplicates when the back and forth isomorphism construction is made).

1 Answers1

1

What you’re missing is that vertex $1$ isn’t the only vertex connected to vertex $2^k$: vertex $2^k$ is also connected to every vertex $n$ such that $p_{2^k}\mid n$, and the set of such $n$ depends on $k$. Thus, these vertices are not duplicates of one another in the sense that you have in mind.

And it’s not hard to verify that $G_0$ does have the extension property. Suppose that I have vertices $a_k$ for $k=1,\ldots,n$, and let $I\subseteq\{1,\ldots,n\}$. Let

$$a=p\prod_{k\in I}p_{a_k}\;,$$

where $p$ is a prime greater than $\prod_{k=1}^np_{a_k}$. Then for $k=1,\ldots,n$ there is an edge between $a$ and $a_k$ if and only if $k\in I$: the factors $p_{a_k}$ for $k\in I$ ensure that there is an edge between $a$ and $a_k$ if $k\in I$, and the factor of $p$ ensures that there is no edge between $a$ and $a_k$ if $k\in\{1,\ldots,n\}\setminus I$.

Brian M. Scott
  • 616,228
  • M Scott : Many thanks – so Hereditary Finite Sets are isomorphic to the Rado / G0 graph when “symmertised”, by removing the direction of the “element of” relation (though now not so hereditary !). Going the other way, looking to apply direction to the G0 graph, the “element of” relation can be defined by giving an edge direction only from a higher vertex number to a lower vertex number. Vertex sets are then defined by the edges directed away from them, so a “directionalised” G0 does then appear to contain infinite copies of each “hereditary finite set”. –  Dec 07 '16 at 09:57
  • @Colin: You’re welcome. I’ve actually only ever seen it described as an undirected graph. When it’s described in terms of hereditarily finite sets, for instance, I’ve seen it described as having an edge between $x$ and $y$ if one of them is an element of the other. Even when the edge has a natural direction, as it has in that construction, I think that it’s assumed to be undirected; occasionally I’ve seen this stated explicitly. – Brian M. Scott Dec 07 '16 at 18:13