Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, February 2, 2010 - 4:30pm

Tom Bohman

Carnegie Mellon

Location

University of Pennsylvania

DRL 2N36

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. 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.