The triangle-free process

Series: 
Combinatorics Seminar
Friday, October 24, 2008 - 15:00
1 hour (actually 50 minutes)
Location: 
Skiles 255
,  
CMU
Organizer: 
Consider the following random graph process. We begin with the empty graph on n vertices and add edges chosen at random one at a time. Each edge is chosen uniformly at random from the collection of pairs of vertices that do not form triangles when added as edges to the existing graph. In this talk I discuss an analysis of the triangle-free process using the so-called differential equations method for random graph processes. It turns out that with high probability the triangle-free process produces a Ramsey R(3,t) graph, a triangle-free graph whose independence number is within a multiplicative constant factor of the smallest possible.