Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.