The triangle-free process

Consider the following stochastic graph process. We begin with G(0), the empty graph on n vertices, and form G(i) by adding a randomly chosen edge e(i) to G(i-1) where e(i) is chosen uniformly at random from the collection of pairs of vertices that neither appear as edges in G(i-1) nor form triangles when added as edges to G(i-1). Let the random variable M be the number of edges in the maximal triangle free graph generated by this process. We prove that asymptotically almost surely M = (-)(n(3/2)root log n). This resolves a conjecture of Spencer. Furthermore, the independence number of G(M) is asymptotically almost surely (-)(root n log n), which implies that the Ramsey number R(3, t) is bounded below by a constant times t(2)/log t (a fact that was previously established by Jeong Hart Kim). The methods introduced here extend to the K(4)-free process, thereby establishing the bound R(4, t) = Omega(t(5/2)/log(2) t). (C) 2009 Elsevier Inc. All rights reserved.