Spanning Subgraphs of Random Graphs

Source abstract

Let G p be a random graph on 2 d vertices where edges are selected independently with a fixed probability p > ¼, and let H be the d -dimensional hypercube Q d . We answer a question of Bollobás by showing that, as d → ∞, G p almost surely has a spanning subgraph isomorphic to H . In fact we prove a stronger result which implies that the number of d -cubes in G ∈ [Gscr ]( n , M ) is asymptotically normally distributed for M in a certain range. The result proved can be applied to many other graphs, also improving previous results for the lattice, that is, the 2-dimensional square grid. The proof uses the second moment method – writing X for the number of subgraphs of G isomorphic to H , where G is a suitable random graph, we expand the variance of X as a sum over all subgraphs of H itself. As the subgraphs of H may be quite complicated, most of the work is in estimating the various terms of this sum.