Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $C_n=\{0,1\}^n$ be the hypercube and denote by $\operatorname{G}(N,p)$ the Erdos-Renyi random graph (edges appear independently with probability $p$). Assume that $N=2^n$. Could one pin down $p=p(n)$ such that we can embed the hypercube into $\operatorname{G}(N,p)$ and vice versa? Is there anything known about similar problems?

share|improve this question
add comment

2 Answers

up vote 9 down vote accepted

$C_n$ has $N n/2$ edges, while $G(N,p)$ has approximately $p N^2/2$ edges. So you're almost surely not going to embed $G(N,p)$ into $C_n$.

For any of the $N!$ possible maps of $C_n$ onto the vertices of $G$, the probability that the edges of $C_n$ all appear is $p^{N n/2}$. The expected number of embeddings is then $N! p^{N n/2}$. As $N \to \infty$, that goes to $+\infty$ if $p > 1/4$ and to $0$ if $p \le 1/4$. So if $p \le 1/4$, the probability of at least one successful embedding goes to $0$ as well.

share|improve this answer
    
thank you, the ankswer is indeed useful! –  TOM Jun 22 '13 at 2:32
add comment

And $1/4$ is indeed the correct threshold probability: Oliver Riordan proved this in 2000 ('Spanning subgraphs of random graphs') by a second moment argument. His paper is much more general, and is still the best place to look for bounds on the appearance threshold for most graphs.

Incidentally, $G_{N,p}$ does embed in $C_n$ if $p$ is small enough, but at the point where the random graph becomes acyclic (above this point it rapidly acquires many cycles, about half of which are odd and therefore don't embed) and at this point $G_{n,p}$ is not so interesting.

share|improve this answer
add comment

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.