1
$\begingroup$

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?

2 Answers 2

1

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
1

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.