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