Discrete Math Seminar: Ethan White

  • Date: 10/30/2018
  • Time: 16:00
Ethan White, UBC

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. 

Other Information: 

Location: ESB 4127