Random graphs contain cubes

A conjecture on a spanning cube in a random graph (proposed by Erdös and Bollobás)
A random graph on \(n = 2^d\) vertices with edge density \(\frac{1}{2}\) contains an \(d\)-cube. }

Alon and Füredi \( ^{[1]}\) showed that this conjecture is true if the random graph has edge density \( p > \frac{1}{2}\) for \( n\) large enough (as a function of \( p\)).

In 2000, Riordin proved the conjecture \( ^{[3]}\), showing that it holds whenever \( p>\frac14\). Furthermore, he shows that the number of \( d\)-cubes in \( G(n,M)\) is asymptotically normally distributed for \( M\) in a certain range. The proof uses the second moment method, and much of the work is in estimating the various terms in the resulting sum.

Bibliography
1 N. Alon and Z. Füredi, Spanning subgraphs of random graphs, Graphs and Combinatorics 8 (1992), 91-94.

2 P. Erdös, Some recent combinatorial problems, Technical Report, University of Bielefeld, Nov. 1990.

3 O Riordan. Spanning subgraphs of random graphs. Combin. Probab. Comput. 9 (2000), no. 2, 125-148.