Random maximal H-free graphs

Abstract:

Given a graph H, a random maximal H-free graph is constructed as follows. Start with n vertices and add edges one by one at random, provided that the resulting graph does not contain H as a subgraph. The process stops when all edges of the complete graph have tried to appear.

The question then is: how many edges will the final graph almost surely have? Erd"os, Suen, and Winkler proved that when H is a triangle, with high probability the final graph will have about n^{3/2} edges. (It is somewhat surprising that in the more restrictive process where one forbids not only a triangle but all odd cycles, the final graph has cn^2 edges, for some constant c.) In this talk, we consider the case where H is an arbitrary complete graph or cycle.