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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
$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.
answered Jun 20, 2013 at 8:19
$\begingroup$
$\endgroup$
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.
