## Discrete Math Seminar: Ethan White

- Date: 10/30/2018
- Time: 16:00

University of British Columbia

The Triangle-Free Process II

This is the second part of a two part series 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). I will present Erdos, Suen, and Winkler's proof that the triangle-free process gives a lower bound on R(3,t) within a logarithmic factor of the best possible. We will see that the triangle-free process results in fewer edges than the odd-cycle free process.

Location: ESB 4127