Constructing an abundance of Rado graphs
Abstract
Rado constructed an (undirected) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m'th position of its binary expansion. It is well known that R is a universal graph in the set I of all countable graphs (since every graph in J is isomorphic to an induced subgraph of R). From other known properties of R (or by approaching R as a random graph) it can easily be deduced that there are edge-disjoint copies of R in the complete denumerable graph KR 0 (since R is self-complementary) and also that some proper subgraphs of R are isomorphic to R (since R is indestructible). In this paper we elaborate on this by focusing on different constructions of graphs isomorphic to the Rado graph R to prove the existence of many pairwise edge-disjoint, many pairwise vertex-disjoint and an abundance of uncountably many different copies of R in R.
