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? 



Embedding a hypercube into the Erdos-Renyi random graph
$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.


