Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-06T08:31:50.220Z Has data issue: false hasContentIssue false

Spanning Subgraphs of Random Graphs

Published online by Cambridge University Press:  01 March 2000

OLIVER RIORDAN
Affiliation:
SFB 343, Universität Bielefeld, Postfach 10 01 31, 33501 Bielefeld,Germany and Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, England (e-mail: [email protected])

Abstract

Let Gp be a random graph on 2d vertices where edges are selected independently with a fixed probability p > ¼, and let H be the d-dimensional hypercube Qd. We answer a question of Bollobás by showing that, as d → ∞, Gp 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.

Type
Research Article
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)