MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
thank you, the ankswer is indeed useful! – TOM Jun 22 '13 at 2:32

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|cite|improve this answer

Your Answer


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.