The triangle-free process

Consider the following stochastic graph process. We begin with G0, the empty graph on n vertices, and form Gi by adding a randomly chosen edge ei to Gi−1 where ei is chosen uniformly at random from the collection of pairs of vertices that neither appear as edges in Gi−1 nor form triangles when added as edges to Gi−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 . This resolves a conjecture of Spencer. Furthermore, the independence number of GM is asymptotically almost surely , which implies that the Ramsey number R(3,t) is bounded below by a constant times t2/logt (a fact that was previously established by Jeong Han Kim). The methods introduced here extend to the K4-free process, thereby establishing the bound R(4,t)=Ω(t5/2/log2t).