Discrete Math Seminar: Ethan White

This is the first part of a two part exposition on the triangle-free process. The triangle-free process begins on an empty graph and adds edges at random, provided no triangle is created with the existing edges. One of the original motivations for this process came from Ramsey Theory. Spencer conjectured that the maximum size of an independent set in a graph resulting from the process should be relatively small, and so the triangle-free process would provide constructions for lower bounds on the Ramsey number R(3,t). Recently, Bohman and Keevash obtained new estimates on independence number of such graphs, which gives a lower bound on R(3,t) within a factor of 4+o(1) of the best know upper bound. In this first part I will discuss random graph processes, with an emphasis on the triangle-free process and the odd-cycle-free process.