- Series
- Combinatorics Seminar
- Time
- Friday, October 24, 2008 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Tom Bohman – CMU
- Organizer
- Prasad Tetali

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.