Discrete Math Seminar: Ethan White
Topic
The Triangle-Free Process II
Speakers
Details
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.
Additional Information
Location: ESB 4127
Ethan White, UBC
Ethan White, UBC
This is a Past Event
Event Type
Scientific, Seminar
Date
October 30, 2018
Time
-
Location