Is there an [added: not super-exponential, better: polynomial] way to compute for a given graph of $n$ vertices (as an adjacency matrix) corresponding natural numbers such that $v_i$ and $v_j$ are adjacent iff $n_i$ and $n_j$ are adjacent in Rado's construction of the Rado graph?
Calculating Rado subgraph from adjacency matrix
2 Answers
An outline of such an algorithm is given in the "Finding isomorphic subgraphs" section of the Wikipedia article you linked to.
In particular, let $A$ be the adjacency matrix of the graph, i.e. a symmetric binary matrix such that $A_{i,j} = 1$ if $v_i$ and $v_j$ are adjacent, and $0$ otherwise. We may then define $n_i$ iteratively as $n_1 := 0$ (actually, any $n_1 \ge 0$ will do) and
$n_i := 2^{1+n_{i-1}} + \sum_{j=1}^{i-1} A_{i,j} 2^{n_j} \quad \forall i > 1.$
The function of the sum term in the construction should be obvious. The $2^{1+n_{i-1}}$ term is there to ensure that $n_i > n_{i-1}$, and thus that $n_i > n_j$ whenever $i > j$. In particular, since $n_i \ge 2^{1+n_{i-1}} > 1+n_{i-1} > n_{i-1}$, we can be sure that $n_j \ne 1+n_i$ for all $i$ and $j$, and thus this extra term introduces no unwanted edges in the subgraph.
Of course, this algorithm is somewhat impractical, since the numbers get large quickly: for an empty graph, it will yield $n_2 = 2$, $n_3 = 8$, $n_4 = 512$ and $n_5 = 2^{513} \approx 2.68 \times 10^{154}$. For non-empty graphs, the numbers will be even larger.
Addendum: In fact, the superexponential growth is unavoidable in general. For example, let $n_1, \dotsc, n_m$ be natural numbers such that the corresponding subgraph of the Rado graph is the complete graph $K_m$. Without loss of generality, sort the numbers so that $n_i > n_j \iff i > j$. Then we must have
$n_i \ge \sum_{j=1}^{i-1} 2^{n_j} \ge 2^{n_{i-1}}, $
and thus, since $n_1 \ge 0$, it follows that $n_i \ge {^{i-2}2}$ for $i > 1$, where ${^k2} = \underbrace{2^{2^{\cdot^{\cdot^{2}}}}}_k$ denotes base-$2$ tetration.
In particular, the smallest numbers forming an $m$-clique in the Rado graph are the $m$ first elements of the sequence given by the recurrence $n_1 = 0$, $n_{i+1} = n_i + 2^{n_i}$. This is sequence A034797 in the OEIS. Its first five terms are $0$, $1$, $3$, $11$ and $2059$; the sixth term is $2059 + 2^{2059} \approx 0.66 \times 10^{620}$.
-
0@Hans Stricker: Answered below (too much for a comment) – 2011-11-22
This is a comment about a graph isomorphic to Rado graph, but with a polynomial time algorithm to find embedding.
Start with this countable graph $H$:
Vertices are pairs $(G,v)$ where $G$ is a finite graph on $\{1,2,\dots,n\}$ for some $n$ and $v$ is a vertex in $G$
There is an edge between $(G,v)$ and (G',v') iff G=G' and there is an edge (v,v') in $G$
so $H$ it is a disjoint sum indexed by natural $n$ of disjoint sums of all $2^{n^2}$ graphs with $n$ vertices.
The graph $H$ has a polynomial-time algorithm to find embedding; namely given graph $G$, the embedding is $v \mapsto (G,v)$.
However, $H$ is not (isomorphic to) the random graph, but you can enlarge it.
Define an "object" as:
- vertex in $H$
- finite set of previously constructed objects
for example $\{(G_1, v_1), \{(G_2, v_2), (G_3, v_3)\}\}$ is an object, assuming $v_i \in G_i$.
Call objects which are vertices of $H$ "type 1" and all others (those which are sets) "type 2".
Define graph H': vertices are objects, and there is an edge between $u$ and $v$:
- if $u$ and $v$ are objects of type 1 then there is an edge between them if there is an edge in $H$
- if $u$ is a vertex of type 1 and $v$ a vertex of type 2, then there is an edge if $u \in v$
- if $u$ and $v$ are objects of type 2 then there is an edge if $u \in v$ or $v \in u$
This graph has extension property (easy) so it's a Rado graph. There is a polynomial time embedding from $H$ to H', so by composition, a polynomial time algorithm to find an embedding from $G$ to H' for any finite $G$.
While vertices of $H$ and H' are not natural numbers, they can be coded using them. The numbers are about size $2^{n^2}$, but this is OK, since they can be written in polynomial time.