ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05C80 Riordan, Oliver, Cambridge University, England Spanning subgraphs of random graphs Let G_{p} be a random graph on 2^{d} vertices where edges are selected independently with a fixed probability p > 1/4, 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 result which can be applied to many other graphs H, improving also previous results for the lattice, i. e., the 2-dimensional square grid.