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?

-

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}$.

-
So I should ask whether there is a polynomial-time and/or -space algorihtm. Should I edit the original question or ask a new one? – Hans Stricker Nov 21 '11 at 17:56
@Hans Stricker: if you want complete graph $K_n$ embedded into Rado graph you need $k$ numbers $x_1, x_2, \dots, x_k$ such that for all $i \neq j$ either $x_i$ has on $x_j$th place 1 or $x_j$ has on $x_i$ place 1. This can only happen when $x_i \geq 2^{x_j}$ or $x_j \geq 2^{x_i}$. Sorting the numbers, $x_{j} \geq 2^{x_{j-1}}$, so it requires tower of $k$ exponents, so the problem cannot be solved if you have fixed number of exponents (it's not en.wikipedia.org/wiki/ELEMENTARY). However, I would not rule out another construction of Rado's graph which has such algorithm. – sdcvvc Nov 21 '11 at 18:16
[In fact, there is such construction] – sdcvvc Nov 21 '11 at 18:23
@sdcvvc: I see you came up with the same counterexample as I did. Great minds think alike. :) – Ilmari Karonen Nov 21 '11 at 18:50
@sdcvvc: You make me curious. – Hans Stricker Nov 22 '11 at 7:02

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:

1. vertex in $H$
2. 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.

-