Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-11T07:02:32.231Z 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: omr10@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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