Grids in random graphs

Threshold probabilities for the existence in a random graph on n vertices of a graph isomorphic to a given graph of order Cn and average degree at least three are investigated. In particular it is proved that the random graph G(n, p) on n vertices with edge probability contains a square grid on En/2 vertices. © 1994 John Wiley & Sons, Inc.