On Graphs Not Containing Prescribed Induced Subgraphs

Given a fixed graph H on t vertices, a typical graph G on n vertices contains many induced subgraphs isomorphic to H as n becomes large. Indeed, for the Gusual model of a random graph G* on n vertices (see [B2]), in which potential edges are independently induced or not each with probability 1/2, almost all such G* contain (1+o(1)n sup t 2 sup -( 2 over t ) induced copies of H as n-> proportional to . Thus, if a large graph G contains no induced copy of H, it deviates from being "typical" in a rather strong way.