PROVED
This has been solved in the affirmative.
If $G$ is a random graph on $2^d$ vertices, including each edge with probability $1/2$, then $G$ almost surely contains a copy of $Q_d$ (the $d$-dimensional hypercube with $2^d$ vertices and $d2^{d-1}$ many edges).
A conjecture of Erdős and Bollobás. Solved by Riordan
[Ri00], who in fact proved this with any edge-probability $>1/4$, and proves that the number of copies of $Q_d$ is normally distributed.
See also
the entry in the graphs problem collection.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #578, https://www.erdosproblems.com/578, accessed 2026-01-16
